\documentclass[12pt, a4paper,english,spanish]{article}
\usepackage{babel}
%\parindent = 10 pt
%\parskip = 11 pt
\usepackage[width=15.5cm, left=3cm, top=2.5cm, height= 24.5cm]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{tikz}
\usetikzlibrary{shadows}
\tikzset{>=latex}

\begin{document}
\shorthandoff{>}
\renewcommand{\refname}{} 

\begin{center}
\large{\textbf{Algoritmos y Estructuras de Datos III}}

\normalsize{Segundo Cuatrimestre de 2012}

\vspace{2mm}

Departamento de Computaci\'on\\
Facultad de Ciencias Exactas y Naturales\\
Universidad de Buenos Aires\\

\vspace{10mm}

\LARGE{\textsc{\textbf{Trabajo Pr\'actico 2}}} \\

\LARGE{Grupo 5}

\vspace{10mm}

\normalsize

\begin{tabular}{c|c|c}
\hline
\textbf{Autor} & \textbf{Correo electr\'onico} & \textbf{LU}\\
\hline
Emilio Ferro & reclarinette2002@yahoo.com.ar& 441$/$00\\    
Marina A. Niikado & mariniik@yahoo.com.ar & 711$/$07\\
Franco Pistasoli & fpistasoli@gmail.com & 194$/$08\\
Ezequiel Schwab & ezequiel.schwab@gmail.com & 132$/$09\\
\hline
\end{tabular}

\end{center}

\vskip 12pt
\rule{\textwidth}{1.2pt}
\vskip 5pt


\newpage

\setcounter{tocdepth}{2}  % para que aparezcan las subsecciones, ademas sacarle el * de la \subsection*{...}
\tableofcontents


\newpage


\section{Problema 1}  

\subsection{Introducci\'on}

En este primer problema, se presenta la siguiente situaci\'on: dado un mapa, con cierta cantidad de ciudades, conectadas entre s\'i mediante rutas o caminos, se pretende saber cu\'anto peso puede transportar un cami\'on, como m\'aximo, desde una determinada ciudad que llamaremos \textit{origen}, hasta alguna otra que llamaremos \textit{destino}. Se sabe que cada tramo que conecta una ciudad con otra lindante tolera a lo sumo un determinado peso. No importa por cu\'antas ciudades haya que pasar (no nos importa el camino m\'as corto), s\'olo nos interesa poder llegar al destino con el 
mayor peso posible.

Para modelar el problema, utilizamos grafos no dirigidos; las ciudades son los v\'ertices (de los cuales se distinguen 2, el origen y el destino) y los caminos son las aristas con sus respectivos pesos. Entonces, nuestro problema pasa a ser, encontrar el camino desde el v\'ertice origen al v\'ertice destino que nos deje ``pasar el mayor peso''.


\subsection{Desarrollo}
Pasamos por varias maneras de ver, entender y resolver el problema.

Para nuestra versi\'on inicial usamos las siguientes estructuras:

\begin{itemize}
\item Un Diccionario que contiene las ciudades.
 
\item Una clase Ciudad: cada ciudad contiene informaci\'on sobre los caminos hacia las vecinas; el peso con el cual, en determinado
momento del algoritmo principal, sabemos que se podr\'ia transportar hasta all\'i; un flag que indica si ya fue visitada, y su nombre.

\item Una clase Camino: cada camino guarda la ciudad vecina y el peso que tolera ese camino entre esas dos ciudades.
\end{itemize}

\subsubsection*{Algoritmo propuesto}

\textbf{Primera versi\'on}

Para esta primera versi\'on, creamos al comienzo del algoritmo un diccionario que guardaba las ciudades del mapa, y para cada ciudad se pod\'ia obtener el conjunto de sus ciudades vecinas, implementado con un arreglo. 

Nuestra idea inicial fue que, partiendo de la ciudad origen (a la cual le seteamos de entrada un peso hasta ella misma con valor infinito; ya veremos por qu\'e), ``mirar'' una ciudad en cada iteraci\'on de nuestro ciclo principal. La ciudad elegida para ver en cada vez, era la que nos entregaba una funci\'on que hab\'iamos llamado \texttt{buscarMaximo}. Esa funci\'on, recorr\'ia TODO el diccionario de ciudades y se fijaba cu\'al de las ciudades que no estaban marcadas como visitadas, ten\'ia su variable de peso con valor m\'aximo. Esto tomaba tiempo lineal para cada b\'usqueda de m\'aximo.

Luego, de la ciudad elegida, obten\'iamos los caminos hacia las ciudades adyacentes o vecinas (en realidad en esta primera versi\'on, termin\'abamos obteniendo s\'olo el nombre, con el cual ten\'iamos que buscar, nuevamente en el diccionario, la ciudad propiamente dicha). Recorr\'iamos esas vecinas, intentando ver con cu\'anto peso pod\'iamos llegar desde nuestra ciudad actual a cada una de sus vecinas. Si en alguna ocasi\'on anterior hab\'iamos logrado llegar a una de ellas con peso mayor del que pod\'iamos llevar viniendo por esta ciudad actual, entonces el peso en esta ciudad vecina no lo cambi\'abamos, de lo contrario se actualizaba con el nuevo peso.  

Luego de haber mirado TODAS las ciudades, nuestro algoritmo nos devolv\'ia el peso con el cual hab\'iamos podido llegar al destino. Lo probamos con los ejemplos de la c\'atedra y funcionaban todos... Agregamos algunos para los que no, y esto se deb\'ia a que necesit\'abamos agregar unos chequeos m\'as. Notamos que para que funcionara, en alguna de las iteraciones ten\'iamos que poder cambiar el valor ya obtenido para la ciudad actual, lo cual parec\'ia raro, pero parec\'ia que funcionaba.

Igualmente ten\'iamos dos grandes problemas. Por un lado, no cumpl\'iamos la complejidad que nos ped\'ian, y por otro lado y m\'as importante, no ten\'iamos totalmente claro el \textit{invariante} de nuestro algoritmo, y por tanto tampoco la certeza de la correctitud del mismo. 

Para tratar de solucionar el problema de la complejidad, probamos con dejar de buscar en cada paso el m\'aximo y s\'olo recorrer las ciudades en un orden aleatorio, lo cual hizo que tuvi\'eramos que agregar mayor cantidad de \texttt{ifs}, comparaciones y chequeos en nuestro algoritmo. Aunque al principio pareci\'o que funcionaba, !`y nos daba una complejidad total de $\mathcal{O}$(tramos)! Lo cual era genial, aunque tambi\'en muy sospechoso. Respecto del invariante, nuestro conocimiento era m\'as oscuro que antes. Finalmente encontramos un caso donde claramente fallaba el algoritmo, y nos dimos 
cuenta de que la idea de esa soluci\'on no ten\'ia ning\'un sentido.

Luego de consultar bastante a los docentes terminamos entendiendo qu\'e ten\'ia que hacer nuestro algoritmo y qu\'e deb\'iamos modificar para lograr tener un invariante que nos diera indicios de que ahora s\'i encontrar\'iamos la ansiada correctitud (aunque todav\'ia no la complejidad).\\


\textbf{Segunda versi\'on}

Para nuestra siguiente versi\'on, empezamos agregando una nueva estructura, una cola de prioridad (implementada con un \textit{heap}), a la que llamamos \textit{frontera}. En la frontera mantendremos ciertas ciudades, y la prioridad de \'estas estar\'a dada por el peso con que se sabe ya se ha podido llegar a cada ciudad.

Entonces, ahora nuestro algoritmo empieza agregando a la ciudad de origen en la frontera. En cada iteraci\'on del ciclo principal se obtiene la ciudad de prioridad m\'axima, quit\'andola de la frontera; en la primera, es la de origen, ya que es la \'unica que hay en la cola. Como antes, se obtienen las vecinas y se les setea su variable peso con el m\'inimo valor entre el peso de la ciudad actual y el peso tolerado por el camino, si es que ese m\'inimo es mayor al peso que la ciudad vecina ya ten\'ia; si no, se la deja como estaba, ya que est\'a claro que no convendr\'ia llegar por ah\'i a dicha ciudad.
A la ciudad origen le hab\'iamos seteado el valor \textit{infinito} (en la implementaci\'on, el m\'aximo n\'umero entero respresentable), entonces, ese m\'inimo ser\'a, para cada ciudad vecina, el valor del peso tolerado. 

M\'as en general, para cualquiera iteraci\'on del ciclo, se intenta saber con cu\'anto peso se puede pasar de una ciudad a otra, teniendo en cuenta el peso actual de la ciudad que se est\'a mirando, el peso actual de su vecino y el peso permitido por el camino que las une.
	
Entonces, nuestro \textit{invariante} es que en cada paso tenemos un conjunto de ciudades que podr\'iamos llamar \textit{confirmadas}, que son las que ya fueron obtenidas como m\'aximo en la cola, y son aquellas que ya fueron visitadas y de las cuales podemos asegurar que el valor del peso que ya tienen seteados es el m\'aximo con el que se puede llegar desde la ciudad origen, ya que si existiera otra ciudad de la que se pudiera llegar con mayor peso, la hubi\'eramos elegido antes de la frontera, ya que tendr\'ia un valor m\'as alto. \'Esta es la idea central, que nos da la seguridad de que nuestro algoritmo encuentra lo que queremos.

Podemos decir que en cada paso, se pueden diferenciar tres clases de ciudades (o conjuntos de ciudades):

\begin{itemize}
\item Las confirmadas
\item Las de la frontera
\item Las desconocidas
\end{itemize}

Como ya dijimos, las confirmadas son aquellas de las que ya s\'e con cu\'anto peso, a lo sumo, puedo llegar desde el origen; en otras palabras, son aquellos nodos del grafo que ya han sido ``consumidos'', por lo que ya no est\'an en la frontera. 

Las ciudades que est\'an en la frontera, luego de cada iteraci\'on, son todas las vecinas de las que ya est\'an confirmadas (y que obviamente todav\'ia no han sido elegidas como ciudades de peso m\'aximo; por eso siguen all\'i, es decir, no est\'an confirmadas a\'un y tienen un valor de peso tentativo).

Las desconocidas son aquellas de las que todav\'ia no se sabe nada y que tienen su peso en cero. No son vecinas de ninguna ciudad confirmada, es decir, ningun camino que recorrimos hasta ahora nos llev\'o hacia ellas.

Nuestro algoritmo terminar\'a por alguna de estas dos razones:

\begin{enumerate}
\item[(1)] Cuando la ciudad que se elija de la frontera sea la ciudad de destino.
\item[(2)] Cuando la frontera est\'e vac\'ia.
\end{enumerate}

?`Como sabemos, si pasa (1), que el algoritmo devuelve el resultado esperado? Sale directamente leyendo el invariante. Como en la primera iteraci\'on del ciclo, la ciudad que se agrega y tambi\'en se elige de la frontera es la de origen, y al comienzo de la segunda iteraci\'on tenemos en la frontera a TODAS las vecinas del origen, de todas ellas elegiremos la de peso m\'aximo; es decir, estamos seguros de que ya evaluamos todas las formas de ``salir'' del origen por cada vecina (las restantes, quedaron todas en la frontera). A medida que avanzamos con las iteraciones, se van a ir sacando (van quedando confirmadas) de la frontera aquellas que en cada ciclo tengan el peso m\'aximo, y a su vez, agregando las vecinas de esos m\'aximos que van saliendo.

Cualquiera de esas vecinas, en el futuro, pueden ser m\'aximo de alguna iteraci\'on. Eventualmente, la ciudad de destino podr\'ia ser agregada a la frontera. Con lo que si estando en la frontera, la ciudad elegida como m\'aximo es la destino, esto implica que NO HAY NING\'UN CAMINO que, saliendo desde el origen, haya permitido llevar hasta alguna ciudad un peso mayor que el que tiene en ese momento la ciudad de DESTINO, ya que si alguna tuviera un peso mayor, \'esa ser\'ia la elegida, en vez de la de destino.

?`Y si se da (2)? Bueno, en este caso lo que sucedi\'o es que la ciudad de destino fue la \'ultima en ser elegida de la frontera, y eso se debe a que, desde el origen y hacia cualquier ciudad del mapa, se puede llegar con un peso mayor (tambien podr\'ia ser igual, y en ese caso podr\'ia ser la \'ultima o una de las \'ultimas) que a la de destino, y por eso es elegida en ultima instancia.

Con lo cual, la propia construcci\'on del algoritmo nos determina su correctitud. \\

Como la primera versi\'on de nuestro algoritmo principal, a saber, \texttt{obtenerMaximo}, no cumpl\'ia con la complejidad pedida (era superior a $\mathcal{O}(|tramos| \; log(|ciudades|))$), por el solo hecho de tener que buscar, en cada iteraci\'on del ciclo principal, el elemento m\'aximo de un diccionario, para el cual se recorr\'ia linealmente, entonces ah\'i fue cuando nos dimos cuenta de la necesidad de usar una estructura m\'as eficiente para extraer este elemento. As\'i es como pasamos a la versi\'on 2, donde decidimos usar una cola de prioridad implementada con un heap. De esta forma, encontrar y extraer el elemento con m\'axima prioridad (en nuestro caso, la ciudad de la frontera con m\'aximo peso transportable desde el origen hasta ella) pas\'o de tener una complejidad lineal a logar\'itmica (asegurada por la complejidad de la operaci\'on de \textit{desencolar} provista por el heap). La prioridad est\'a dada por el peso de cada ciudad de la frontera, y el pr\'oximo elemento a desencolar del heap es la ciudad con el mayor peso (luego esto es un \textit{max-heap}).

A pesar de estar usando una estructura que mejoraba la complejidad, no logr\'abamos tener la pedida por el enunciado del ejercicio. Esto se deb\'ia a que, en una misma iteraci\'on, los pesos de las ciudades de la frontera pod\'ian cambiar. Luego, la ciudad que ser\'ia la pr\'oxima a elegir como \textit{confirmada}, antes de realizado alg\'un cambio en el peso de las ciudades de la frontera, pod\'ia llegar a cambiar de una iteraci\'on a la otra. Si estos cambios no se ve\'ian reflejados en el heap, entonces el algoritmo probablemente fallar\'ia y se romper\'ia el invariante discutido anteriormente. Para que los cambios se reflejaran en el heap, lo que hac\'iamos es, entonces, cambiar el peso de esta ciudad y ``reubicarla'' en el heap. Reubicarla significa reestablecer el invariante del heap (es decir, la prioridad de cada nodo es mayor o igual que la de sus hijos, si los tiene, y todo sub\'arbol es un heap). Entonces, busc\'abamos el elemento en el heap, ya con su valor de peso incrementado\footnote{Notar que el peso de cualquier ciudad siempre se ve a lo sumo incrementado de una iteraci\'on a otra; nunca decrece, ya que siempre tratamos de mejorar el peso m\'aximo que se puede trasladar desde el origen hasta esta ciudad}, lo remov\'iamos del heap y lo volv\'iamos a insertar en \'el. A pesar de ser correcto este procedimiento, para que se siga cumpliendo el invariante del algoritmo principal, la complejidad volv\'ia a verse empeorada. El problema estaba en que la estructura de heap que est\'abamos usando buscaba un elemento arbitrario en \'el en tiempo lineal en la cantidad de nodos del heap. Aunque volver a insertarlo no era un problema para nosotros (pues la complejidad era logar\'itmica; menos que lineal), el hecho de tener que buscarlo s\'i lo era, de esta forma superando la complejidad pedida. 

Debido a todo esto, era claro que la operaci\'on de encontrar un elemento arbitrario en el heap deb\'ia tomar un tiempo menor que lineal (idealmente, constante). Ac\'a es donde empieza nuestra tercera versi\'on del algoritmo.\\


\textbf{Tercera versi\'on}

La tercera versi\'on del algoritmo \texttt{obtenerMaximo} utiliza una cola de prioridad \textit{extendida}. Esta cola le agrega mayor funcionalidad a la cola de prioridad que implementa \textit{Java} con la clase \texttt{PriorityQueue}, proporcion\'andole una funci\'on adicional que, dado un elemento presente en el heap, al que se le vio alterada su prioridad, lo reubica en \'el para que no se viole el invariante del heap. Esta operaci\'on, denominada \texttt{reubicar}, se diferencia de la que hab\'iamos implementado en la versi\'on anterior, ya que ahora solamente acceder\'iamos en tiempo constante al elemento al cual queremos cambiarle la prioridad, y lo reacomodar\'iamos en el heap en tiempo logar\'itmico (evitando tener que removerlo e insertarlo nuevamente con la nueva prioridad). Lo que antes tomaba tiempo lineal ahora pasa a tomar tiempo logar\'itmico en la cantidad de elementos del heap (o sea, en la cantidad de ciudades de la frontera).

Sin embargo, para lograr que esta operaci\'on fuera de orden logar\'itmico, tuvimos que extender las operaciones b\'asicas de la cola de prioridad (encolar, desencolar, pr\'oximo) y manejar cuestiones de bajo nivel del heap que la implementa. A tales efectos, creamos una estructura interna en la cola extendida llamada \texttt{heap}, que es un arreglo din\'amico (objeto \textsc{ArrayList} de Java), el cual contiene las ciudades actualmente en la frontera, y es esencialmente un arreglo con invariante de heap. A esta estructura le sumamos un \textsc{HashMap} que tiene ciudades como claves y naturales como significados. A este hash lo llamamos \texttt{posEnHeap} y su prop\'osito es el de mantener, para cada ciudad, la posici\'on actual en el arreglo \texttt{heap}. Tambi\'en puede pensarse al \texttt{posEnHeap} como un arreglo de punteros al heap. Esta informaci\'on result\'o esencial a la hora de buscar un elemento arbitrario en la cola de prioridad, al poder obtener ahora en $\mathcal{O}(1)$ la posici\'on exacta de una ciudad cualquiera en el heap.

Otras operaciones que tuvimos que proveerle a nuestra cola de prioridad extendida, a la cual llamamos \texttt{PriorityQueueExt}, fueron las de ``subir'' y ``bajar'' un elemento cualquiera del heap. Estas operaciones se usan para reestablecer el invariante de la estructura y son funciones privadas de la clase. 

$\newline$

Nuestro algoritmo \texttt{obtenerMaximo} entonces se puede resumir as\'i:

\begin{small}

\begin{verbatim}
   1. Inicializacion: poner peso inicial infinito a la ciudad origen y 
      agregarla a la frontera F.
   
   2. Mientras F no sea vacia, hacer:
   
         Obtener c, la ciudad en F que tiene el mayor peso que se puede 
         trasladar desde el origen hasta el momento, de entre todas las
         ciudades de la frontera, y marcarla como confirmada.
         
         Si c es la ciudad destino, parar.
         
         Para cada vecino v de c no confirmado aun, hacer:
           
            Si el peso maximo que se podia trasladar hasta v es menor al
            que se puede trasladar ahora si se viene por c,
              
               Cambiar el peso de v con este nuevo peso
               
               Si v era una ciudad de la clase de las desconocidas,
               
                  Agregar v a F
                  
               Si no (es decir v ya esta en F),
                  
                  Reubicar v en F (reflejar el nuevo peso de v en F)
                  
               FinSi
               
            FinSi
            
         FinPara
         
      FinMientras
\end{verbatim}

\end{small}
    

\subsubsection*{Complejidad}
En esta secci\'on se presenta un an\'alisis de la complejidad (en peor y mejor caso) del algoritmo \texttt{obtenerMaximo}, que es el que resuelve el problema.\\

\textbf{Peor caso}

Refiri\'endonos al c\'odigo Java de \texttt{obtenerMaximo}, observamos que su complejidad en peor caso se puede calcular en dos partes. \\

\begin{small}
\texttt{public int obtenerMaximo(String ciudadOrigen, String ciudadDestino,} \\ \hspace*{9.5cm} \texttt{ArrayList<String> caminos)}
\begin{algorithmic}[1]
\State $generarCiudades(ParseAVecinos(caminos));$ \Comment{$\mathcal{O}(M)$}
\State $Ciudad \; origen = ciudades.get(ciudadOrigen);$ \Comment{$\mathcal{O}(1)$}
\State $origen.setPeso(Integer.MAX\_VALUE);$ \Comment{$\mathcal{O}(1)$}
\State $Ciudad \; destino = ciudades.get(ciudadDestino);$ \Comment{$\mathcal{O}(1)$}
\State $PriorityQueueExt<Ciudad> \; frontera = new \; PriorityQueueExt<Ciudad>();$ \Comment{$\mathcal{O}(1)$}
\State $frontera.encolar(origen);$ \Comment{$\mathcal{O}(1)$}
\While{$(!frontera.isEmpty())$} \Comment{Ver m\'as adelante}
	\State $Ciudad \; prox = frontera.getMax();$ \Comment{$\mathcal{O}(\log N)$}	
	\State $prox.confirmar();$ \Comment{$\mathcal{O}(1)$}
	\If{$(prox.equals(destino))$} \Comment{$\mathcal{O}(1)$}
		\State $break;$
	\EndIf
	\For{$(Camino \; vecino: \; prox.getVecinos())$} \Comment{Ver m\'as adelante}
		\If{$(!vecino.getCiudad().estaConfirmada())$} \Comment{$\mathcal{O}(1)$}
			\State $int \; pesoAnteriorVecino = vecino.getCiudad().getPeso();$ \Comment{$\mathcal{O}(1)$}
			\State $int minimo = Math.min(prox.getPeso(), vecino.getPesoTolerado());$ \Comment{$\mathcal{O}(1)$}
			\If{$(pesoAnteriorVecino < minimo)$} \Comment{$\mathcal{O}(1)$}
				\State $vecino.getCiudad().setPeso(minimo);$ \Comment{$\mathcal{O}(1)$}
				\If{$(pesoAnteriorVecino == 0)$}	 \Comment{$\mathcal{O}(1)$}
					\State $frontera.encolar(vecino.getCiudad());$ \Comment{$\mathcal{O}(\log N)$}
				\Else 
					\State $frontera.reubicar(vecino.getCiudad());$ \Comment{$\mathcal{O}(\log N)$}
				\EndIf
			\EndIf
		\EndIf
	\EndFor
\EndWhile 
\State $return \; destino.getPeso();$
\end{algorithmic}
\bigskip
\end{small}

Llamando $T_{oM}$ al tiempo en peor caso del algoritmo \texttt{obtenerMaximo}, $T_{init}$ a la complejidad de la inicializaci\'on (l\'ineas 1 a 6) y $T_{ciclo}$ al tiempo que toma en peor caso el ciclo principal del algoritmo (l\'ineas 7 a 27), tenemos que $T_{oM}(M,N) = T_{init}(M) + T_{ciclo}(M,N)$, donde llamamos $M$ a la cantidad de aristas del grafo a recorrer y $N$ a la cantidad de v\'ertices del mismo. A continuaci\'on desarrollamos cada uno de los tiempos.

\begin{itemize}
\item $T_{init}$ En la inicializaci\'on, el arreglo \textit{caminos}, que contiene $3M$ elementos, se pasa al m\'etodo \texttt{ParseAVecinos}, el cual lo recorre en forma lineal y usa operaciones de la clase \textsc{ArrayList} (\texttt{size, get, add}), todas de tiempo constante. Por lo tanto, el m\'etodo resulta $\mathcal{O}(3M) = \mathcal{O}(M)$. 

El arreglo devuelto por \texttt{ParseAVecinos} lo procesa \texttt{generarCiudades}, que arma un diccionario implementado con la clase \textsc{HashMap} de Java que contiene a todo el conjunto de ciudades pasado por par\'ametro a la funci\'on principal Como \texttt{generarCiudades} debe recorrer todos los tramos entre dos ciudades, termina recorriendo todas las aristas del grafo. Por cada arista realiza todas operaciones en tiempo constante (operaciones \texttt{put, get, containsKey} de \textsc{HashMap}, y \texttt{add} de \textsc{ArrayList}. Podemos asumir que las tres primeras operaciones se realizan en tiempo constante, habiendo definido una funci\'on de hash buena para la clase \textsc{Ciudad}. El \textit{hashcode} de un objeto de tipo \textsc{Ciudad} nos permite que las ciudades se distribuyan apropiadamente en los \textit{buckets} de la tabla de hash, haciendo que la b\'usqueda y obtenci\'on de un elemento en la tabla de hash se haga eficientemente. Dicho todo esto, \texttt{generarCiudades} resulta tambi\'en $\mathcal{O}(M)$. Por lo tanto, la l\'inea 1 se ejecuta en tiempo $\mathcal{O}(M) + \mathcal{O}(M) = \mathcal{O}(M)$. 

El resto de las l\'ineas en la inicializaci\'on se realizan en tiempo constante. Cabe aclarar que la complejidad de la l\'inea 5 (constructor de la clase \textsc{PriorityQueueExt} se hace en tiempo constante (ya que a su vez llama a constructores por defecto de las clases \textsc{HashMap}, \textsc{ArrayList} y \textsc{PriorityQueue}). En la l\'inea siguiente, se llama al m\'etodo \texttt{encolar} de la clase \textsc{PriorityQueueExt}, que como en este momento representa una cola de prioridad vac\'ia, entonces encolar un elemento se hace en $\mathcal{O}(1)$. 

Concluimos entonces que $T_{init} = \mathcal{O}(M)$.


\item $T_{ciclo}$ Este ciclo (l\'ineas 7 a 27) se ejecuta si y s\'olo si la cola de prioridad (\textit{frontera}) contiene al menos un elemento. En la l\'inea 8 se llama al m\'etodo \texttt{getMax} de la clase \textsc{PriorityQueueExt}. Esta operaci\'on obtiene el pr\'oximo elemento de la cola de prioridad, llamando al m\'etodo \texttt{poll} de la superclase (\textsc{PriorityQueue}), que toma tiempo logar\'itmico en la cantidad de elementos de la cola, y a operaciones que actualizan las dos estructuras internas de la subclase. Como estas actualizaciones involucran operaciones que acceden en $\mathcal{O}(1)$ a estas estructuras, no afectan a la complejidad logar\'itmica de \texttt{getMax}. Adem\'as en este m\'etodo se llama a la funci\'on \texttt{bajar} que es tambi\'en logar\'itmica (ya que consiste en reestablecer el invariante del heap, operaci\'on que toma tiempo en peor caso la altura del \'arbol, que es igual a $log_2(N)$). Luego, \texttt{getMax} tiene costo $\mathcal{O}(log N)$, ya que la frontera tiene a lo sumo $N$ (en realidad $N-1$) elementos en alguna iteraci\'on del ciclo \texttt{while}. En las siguientes cuatro l\'ineas se realizan operaciones en tiempo constante (el \texttt{if} de l\'inea 10 detiene el algoritmo, as\'i que no aporta al peor caso). 

Entre las l\'ineas 13 y 26 aparece otro ciclo (\texttt{for}) que se ejecuta tantas veces como ciudades vecinas (adyacentes) tenga la ciudad \textit{prox}. En principio podr\'iamos pensar que este ciclo se va a ejecutar a lo sumo la cantidad de nodos del grafo, pero veremos que esta cota es muy grosera. Las dos \'unicas l\'ineas que aportan a la complejidad del \texttt{for} son la 20 y 22. En la primera se llama a \texttt{encolar}, una operaci\'on de \textsc{PriorityQueueExt}, que tiene la misma complejidad que \texttt{getMax}, pues realiza una tarea similar. En \texttt{encolar}, se llama al m\'etodo \texttt{add} de la superclase (que es logar\'itmica), se llama al m\'etodo \texttt{put} de \textsc{HashMap} (que sabemos que tiene costo constante, pues usamos una funci\'on de hash buena), y luego se llama a \texttt{subir}, que, al igual que \texttt{bajar}, tiene costo logar\'itmico en peor caso. Por lo tanto, la complejidad de \texttt{encolar} es $\mathcal{O}(log N)$. 

En la l\'inea 22 se llama a \texttt{reubicar}, m\'etodo de \textsc{PriorityQueueExt}, que toma una ciudad y la reubica en el heap para que no se viole su invariante. Al haber implementado esta clase de forma conveniente para poder buscar un elemento arbitrario en el heap en $\mathcal{O}(1)$, la operaci\'on de reubicar un elemento termina costando $\mathcal{O}(log N)$. Esto es porque en \texttt{reubicar} se llama al m\'etodo \texttt{get} de \texttt{HashMap}, operaci\'on de tiempo constante, y luego a \texttt{subir}, que ya vimos que es logar\'itmica. ?`Qu\'e hubiera pasado si no us\'abamos la estructura de la tabla de hash (\textit{posEnHeap}) para almacenar la posici\'on de cada ciudad en el heap? No hubi\'eramos podido acceder directamente a una ciudad arbitraria en el heap, y la \'unica forma de buscarla hubiese sido recorrer linealmente todos los nodos del heap. Esto ya ir\'ia en detrimento de la cota de complejidad pedida por el enunciado.

Dicho todo esto, ahora analicemos la complejidad de $T_{ciclo}$. 

Podemos ver (por la l\'inea 10) que el algoritmo para cuando \textit{prox} es la ciudad destino. Si la ciudad destino fuera la \'ultima en elegir como \textit{confirmada}, entonces estar\'iamos viendo la mayor cantidad de veces que puede ejecutarse este ciclo. Partiendo de que sabemos, por enunciado, que es posible ir de una ciudad a otra cualquiera en el mapa, sabemos entonces que el grafo que estamos representando es conexo. Luego, en la primera iteraci\'on, al entrar al \texttt{while}, la frontera s\'olo tiene un elemento (la ciudad origen). Pero al desencolarla, queda vac\'ia. Sin embargo, como la ciudad origen debe tener al menos una ciudad vecina (por existencia de un destino), entonces en la pr\'oxima iteraci\'on, la frontera tendr\'a al menos un elemento. Cuando volvemos a entrar en el ciclo \texttt{while} (se sigue cumpliendo la guarda), de la frontera nuevamente se extrae la pr\'oxima ciudad a quedar confirmada. Suponiendo que esta ciudad no es la de destino, entonces seguramente tiene que haber alguna otra ciudad en el conjunto de ciudades ``desconocidas'', con lo cual la frontera no qued\'o vac\'ia al extraer la pr\'oxima ciudad. Siguiendo esta idea, vemos que la frontera est\'a vac\'ia si y s\'olo si se han confirmado TODAS las ciudades del mapa (o equivalentemente, los v\'ertices del grafo). Por lo tanto, sabemos que el ciclo \texttt{while} principal se ejecuta a lo sumo $N$ veces. Por otro lado, el \texttt{for}, que dijimos que podr\'iamos acotarlo con $N$, pensando que se ejecuta a lo sumo tantas veces como ciudades existan, en realidad se ejecuta exactamente el grado del v\'ertice \textit{prox} ($d_{prox}$), es decir, la cantidad de vecinos de \textit{prox}.

Por lo tanto, 

$$T_{ciclo} = \sum_{i=1}^{N} \left( \log N + d_{v_i} \log N \right) = \sum_{i=1}^{N} \log N + \sum_{i=1}^{N} d_{v_i} \log N = N \log N + 2M \log N $$ 

ya que la suma de los grados de cualquier grafo es igual al doble de la cantidad de aristas.
\end{itemize}

Entonces, 

$$T_{oM} = M + N \log N + 2M \log N = M + (N+2M) \log N$$ 

Al ser el grafo conexo, la cantidad de aristas es al menos $N-1$ y mucho menor a $\frac{n(n-1)}{2}$ (es decir, la cantidad de aristas en un grafo completo), ya que por haber consultado a uno de los docentes, sabemos que el grafo es planar (y tiene muchas menos aristas que uno completo).

Como $N = \mathcal{O}(M)$ (por conexidad), entonces $N+2M \in \mathcal{O}(M)$, y por esto podemos decir que 

$$T_{oM} = M + (N+2M) \log N = M + M \log N \in \mathcal{O}(M \log N)$$ 

que equivale a $\mathcal{O}(|tramos| \log (|ciudades|))$, la complejidad pedida por enunciado.\\


\textbf{Mejor caso}

El mejor caso del algoritmo \texttt{obtenerMaximo} se da cuando la ciudad destino es vecina del origen, y el mayor peso se da yendo simplemente por el tramo que las une; m\'as a\'un, cuando la ciudad origen s\'olo tiene como vecina a la ciudad destino. En este caso el \texttt{while} principal se ejecuta s\'olo dos veces, y el algoritmo tiene complejidad $\Omega(M)$.

\subsection{Resultados}

En esta secci\'on se analizan distintos casos de test para el algoritmo \texttt{obtenerMaximo}, junto a sus respectivos gr\'aficos de complejidad temporal en peor y mejor caso. 

Dado el grafo que representa el mapa de las ciudades, sabemos que es conexo, y entonces la cantidad de aristas est\'a acotada. M\'as precisamente, si $N$ es la cantidad de ciudades y $M$ la cantidad de tramos, entonces $N-1 \leq M \leq \frac{N(N-1)}{2}$, ya que un grafo de $N$ v\'ertices necesita al menos $N-1$ aristas para ser conexo, y tiene a lo sumo $\frac{N(N-1)}{2}$ aristas (que si tuviera exactamente esa cantidad, ser\'ia completo).

Por lo tanto, analizaremos dos casos: cuando el grafo es conexo y tiene ``pocas'' aristas (aproximadamente $N$), y cuando es completo.

Para los tests de complejidad en peor caso tuvimos en cuenta lo siguiente:

\begin{itemize}
\item El algoritmo \texttt{obtenerMaximo} ejecuta el \texttt{while} principal $N$ veces, es decir que la \'ultima ciudad en ser \textit{confirmada} resulta ser la de destino. 

\item Para cualquier corrida del algoritmo, si el ciclo principal se ejecuta $N$ veces, entonces hay $N$ extracciones de la cola de prioridad \textit{frontera} (o sea, \texttt{getMax} se llama $N$ veces en total) y $N$ inserciones en la cola (o sea \texttt{encolar} se ejecuta $N$ veces en total).

\item Import\'o saber cu\'antas veces se llama a \texttt{reubicar}, ya que cuanto m\'as veces se llama, mayor es la complejidad total. \'Este es el factor determinante que nos muestra el peor caso que podr\'ia ocurrir; al saber que la ciudad destino es la \'ultima en ser confirmada, la cantidad de veces que hagamos \texttt{getMax} \'o \texttt{encolar} siempre ser\'a $N$, y esto no nos permitir\'ia encontrar el peor caso posible. En cambio, el \texttt{reubicar} s\'i; la cantidad de veces que hay que reubicar un nodo en el heap \textit{frontera} no siempre es constante.        
\end{itemize}


\subsubsection*{Peor caso (grafo completo)}
Al tomar un grafo completo, $M = \frac{N(N-1)}{2}$, y como el peor caso del \texttt{obtenerMaximo} es $\mathcal{O}(M \log N)$, esto equivale a $\mathcal{O}(\frac{N(N-1)}{2} \log N)$. 

El test que produce el siguiente gr\'afico es \texttt{TestPeorCasoCompleto()}.  

%PEOR CASO COMPLETO (TOMANDO M=N(N-1)/2) 
\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Ciudades$,ylabel=tiempo en ms
	]
	
\addplot[green,domain=1:1450] {((x*(x-1)/2)*ln(x)/ln(2))/1000}; %lo hago asi pq es completo
\addplot table {peor_caso_completo_chris.txt};
\legend{$((N*(N-1)/2)*log_2(N))/1000$,algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variacion del tiempo en peor caso (tomando un grafo completo) con respecto a la cantidad de ciudades del problema.}
\label{}
\end{figure}

\vspace{0.5cm}

Como vemos en el gr\'afico, la curva de complejidad de nuestro algoritmo se encuentra totalmente por debajo de la cota te\'orica. Adem\'as, ambas tienen forma de una funci\'on cuadr\'atica y son parecidas, ya que al estar considerando un grafo completo, la complejidad te\'orica pasa a ser un producto de un logaritmo y una cuadr\'atica. 


\subsubsection*{Mejor caso (grafo completo)}

Para el mejor caso, la complejidad te\'orica pasa a ser $\Omega(M)$, ya que la inicializaci\'on del \texttt{obtenerMaximo} toma tiempo lineal en $M$, pero al entrar al \texttt{while}, las \'unicas operaciones relevantes en cuanto a la complejidad son: encolar la ciudad origen, desencolarla y encolar su (\'unico) vecino. Estas tres operaciones son de tiempo constante, ya que al principio, \textit{frontera} est\'a vac\'ia. Como el pr\'oximo elemento a ser desencolado de la frontera resulta ser el destino, el algoritmo finaliza.

El test que produce el siguiente gr\'afico es \texttt{TestMejorCasoCompleto()}.  

%MEJOR CASO (ORIGEN Y DESTINO UNIDOS, ORIGEN CON SOLO 1 VECINO (EL DESTINO)) (ESTE VA)
\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Ciudades$,ylabel=tiempo en ms
	]
	
\addplot[green,domain=1:800] {(x*(x-1)/2)/5000}; 
%\addplot table {mejor_caso_origen_con_solo_un_vecino_destino.txt};
\addplot table {mejor_caso_origen_con_solo_un_vecino_destino_+50.txt};
\legend{$(N*(N-1)/2)/5000$,algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variacion del tiempo en mejor caso en un grafo completo con respecto a la cantidad de ciudades del problema.}
\label{}
\end{figure}

\vspace{0.5cm}

Observando las dos curvas, notamos que el tiempo de nuestro algoritmo es mayor o igual a la funci\'on cuadr\'atica $\frac{\frac{N(N-1)}{2}}{5000}$ en todo el dominio. Esto nos dice que encontramos una cota inferior para la complejidad de nuestro algoritmo; es decir que \texttt{obtenerMaximo} es $\Omega(M)$. 

El resultado es el que esper\'abamos, ya que el mejor caso ocurre cuando la ciudad origen est\'a directamente conectada con la ciudad destino, y no tiene otra ciudad vecina. Es l\'ogico que el algoritmo s\'olo demore en armar el grafo (inicializaci\'on), y que el ciclo \texttt{while} lo haga en tiempo constante (y s\'olo lo ejecuta 2 veces). 



\subsubsection*{Peor caso (grafo conexo minimal)} 

En este caso mostramos un grafo conexo casi minimal, o sea con aproximadamente el mismo n\'umero de v\'ertices y aristas ($M \approx N$). 

El test que produce el siguiente gr\'afico es \texttt{TestPeorCasoNoCompleto()}.  

%PEOR CASO CONEXO CASI MINIMAL(TOMANDO M=N) 
\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Ciudades$,ylabel=tiempo en ms
	]
	
\addplot[green,domain=1:2000] {(x + x*ln(x)/ln(2))/500}; 
\addplot table {peor_caso_no_completo_chris.txt};
\legend{$(N + N*log_2(N))/500$,algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variacion del tiempo en peor caso (tomando un grafo conexo casi minimal) con respecto a la cantidad de ciudades del problema.}
\label{}
\end{figure}

\vspace{0.5cm}

Cuando el grafo es conexo y pr\'acticamente minimal (este caso), $M$ es casi $N$, y el algoritmo tarda $\mathcal{O}(N log N)$. Observando la curva de complejidad te\'orica vemos que la de nuestro algoritmo est\'a acotada superiormente por \'esta, salvo para el intervalo que comprende de 0 a 200 ciudades aproximadamente. Luego de 200 vemos que nuestro algoritmo se comporta como la curva verde. Notemos que los tiempos son (mucho) mejores que el peor caso del grafo completo. Esto es ya que en el completo nos daba una complejidad en parte cuadr\'atica y logar\'itmica, ya que ten\'iamos casi $N^2$ aristas, en cambio ac\'a la cantidad de aristas y nodos es casi la misma (luego tenemos una complejidad menor).  



\subsubsection*{Mejor caso (grafo conexo minimal)} 

En este caso mostramos un grafo conexo minimal, con $M=N$.

El test que produce el siguiente gr\'afico es \texttt{TestMejorCasoNoCompleto()}.  


%MEJOR CASO CONEXO CASI MINIMAL(TOMANDO M=N) 
\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Ciudades$,ylabel=tiempo en ms
	]
	
\addplot[green,domain=1:50000] {x/10000}; 
\addplot table {mejor_caso_no_completo.txt};
\legend{$N/10000$,algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variacion del tiempo en mejor caso (tomando un grafo conexo minimal) con respecto a la cantidad de ciudades del problema.}
\label{}
\end{figure}

\vspace{0.5cm}

En este caso vemos que la complejidad del algoritmo est\'a acotada inferiormente por la cota te\'orica ($\Omega(N)$).


$\linebreak$

Habiendo analizado todos los gr\'aficos, vemos que para grafo completo, en el mejor caso, para una cantidad menor o igual a 800 ciudades, el algoritmo tarda a lo sumo 80ms, mientras que esta cantidad es muy inferior a la que tarda en el peor caso (1300ms aproximadamente). Esto nos permite afirmar que tanto el mejor como el peor caso est\'an bien elegidos.

Para el grafo no completo, tanto el peor como el mejor caso se ejecutan r\'apido. Y notamos que el mejor caso del no completo es mucho mejor que el del grafo completo. Es l\'ogico, ya que en el completo se tiene que inicializar un diccionario de $M \approx N^2$ elementos, mientras que para el no completo, $M=N$. Adem\'as, el \texttt{while} del algoritmo toma tiempo constante en ambos casos.


\subsubsection*{Otros tests}

\textbf{Test de pesos aleatorios para un grafo no completo} \\

En este gr\'afico podemos ver el resultado de la ejecuci\'on del test \texttt{TestCasoAzarNoCompleto()}, el cual testea la funci\'on \texttt{obtenerMaximo()} para un grafo no completo con aristas con pesos aleatorios.


\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Ciudades$,ylabel=tiempo en ms
	]
	
%\addplot[green,domain=1:2000] {x/10000}; 
\addplot table {azarNoCompleto.txt};
\legend{algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variacion del tiempo de ejecuci\'on (tomando un grafo conexo minimal) con respecto a la cantidad de ciudades del problema, donde los pesos de las aristas son aleatorios.}
\label{}
\end{figure}

\vspace{0.5cm}



\textbf{Test de pesos aleatorios para un grafo completo} \\

En este gr\'afico podemos ver el resultado de la ejecuci\'on del test \texttt{TestCasoAzarCompleto()}, el cual testea la funci\'on \texttt{obtenerMaximo()} para un grafo completo con aristas con pesos aleatorios.


\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Ciudades$,ylabel=tiempo en ms
	]
	
%\addplot[green,domain=1:2000] {x/10000}; 
\addplot table {azarCompleto.txt};
\legend{algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variacion del tiempo de ejecuci\'on (tomando un grafo completo) con respecto a la cantidad de ciudades del problema, donde los pesos de las aristas son aleatorios.}
\label{}
\end{figure}

\vspace{0.5cm}



$\newline$

Podemos observar a partir de estos dos gr\'aficos, que los tiempos obtenidos son parecidos a los del peor caso para grafo completo y no completo, pero siguen siendo menores. Esto hace que podamos corroborar que los peores casos del algoritmo fueron elegidos correctamente. 

Notamos que en estos casos de pesos aleatorios, se ejecuta menos veces el ciclo \texttt{while} principal, ya que la ciudad destino no tiene porqu\'e tener el menor peso, y por ende no hace falta recorrer todas las ciudades. Y adem\'as \texttt{reubicar} se llama una cantidad de veces aleatoria, y por eso el tiempo en algunos casos se asemeja al peor, y en otros no tanto. 




\subsection{Conclusiones}

Destaquemos las conclusiones de este ejercicio:

\begin{itemize}
\item El uso de una cola de prioridad para guardar elementos de la frontera result\'o ser una estructura conveniente para lograr la cota de complejidad temporal pedida por el enunciado, ya que sus operaciones tienen un orden de complejidad eficiente y, mediante una extensi\'on de la estructura de datos, se logr\'o que la b\'usqueda de un elemento arbitrario se haga en $\mathcal{O}(1)$. 

\item Al saber que nuestro grafo era conexo, pudimos encontrar una cota para la complejidad que hab\'iamos alcanzado para lograr la pedida por el enunciado.

\item Los gr\'aficos de la secci\'on \texttt{Resultados} nos permitieron corroborar las cotas te\'oricas alcanzadas y expuestas en la secci\'on de \texttt{Complejidad}.  
\end{itemize}







\newpage








\section{Problema 2} 
\subsection{Introducci\'on}
En este problema se tiene un campo, al que se le colocan una cantidad de vallas con cierta altura, orientadas de forma vertical u horizontal. Un par de vallas s\'olo se pueden superponer en un punto. Seg\'un la disposici\'on y altura de las mismas, quedar\'an \'areas del campo a resguardo de la plaga. 
Nos interesa encontrar los sectores del campo que est\'an encerrados por vallas de altura mayor o igual a lo que pueden saltar las langostas, obteni\'endose as\'i, la superficie total que queda a salvo de estos insectos. 
\subsection{Desarrollo}
\subsubsection*{Algoritmo propuesto}
Para llegar a la soluci\'on del problema, pasamos por infinidad de algoritmos que no funcionaban (o s\'olo funcionaban para algunos grafos en particular). Lo que s\'i, siempre tuvimos en claro desde el principio fue que, dado un grafo en donde las aristas representan a las vallas, y los nodos a los extremos de estas vallas, el problema se trasladaba a encontrar ciclos en el grafo, de manera que las aristas tengan altura mayor o igual a lo que saltan las langostas y, una vez encontrados, calcular su superficie. Entonces, podemos dividir en dos partes el problema principal: 
\\
\begin{itemize}
\item Hallar todos los ciclos v\'alidos. 
\item Calcular la superficie total.
\end{itemize}
Estas 2 partes se fueron subdiviendo en subproblemas a medida que \'ibamos estudiando el problema (gran parte haciendo grafos en papel). Una vez que llegamos a la soluci\'on final, nuestro algoritmo qued\'o dividido en los siguientes subalgoritmos o pasos:
\\
\begin{itemize}
\item Dividir las vallas que se intersecan y ordenarlas.
\item Crear el grafo y eliminar las vallas que tienen una altura menor a lo que saltan las langostas
\item Eliminar vallas fuera de ciclos
\item Para cada ciclo, obtener el ciclo que ``engloba'' a los dem\'as subciclos, es decir, el ciclo de mayor superficie.
\item Subdividr cada ciclo encontrado en el punto anterior en rectangulos
\item Para cada ciclo subdividido en rect\'angulos, hallar la superficie de cada rect\'angulo.
\end{itemize}

Empecemos explicando cada punto. Una vez hecho en papel el grafo del ``HOLA'' dado por la c\'atedra, llegamos a la conclusi\'on de que era necesario dividir las vallas que se superpon\'ian en un punto (funci\'on $ \texttt{dividirVallas}$) , para que sea mas c\'omodo cuando tengamos que recorrer el grafo buscando ciclos. Una vez llegada a esta conclusi\'on, pensamos inmediatamente en la complejidad. Si divid\'iamos las vallas, y despu\'es recorr\'iamos las vallas del grafo, cambiar\'ia la complejidad? Seguir\'iamos recorriendo el grafo en O(vallas)? Esto, como en un principio pensamos en que no ibamos a tener problemas ya que parecia ser que el numero de vallas iba a quedar a lo sumo multiplicado por una constante de la cantidad de vallas original, lo dejamos as\'i (cosa que no es asi, pero por suerte se nos arreglo este tema autom\'aticamente por como continuamos el algoritmo como veremos mas adelante cuando analicemos la complejidad).

\vspace{0.5cm}

Con las vallas ya divididas, pasamos a la creaci\'on del grafo no dirigido ($ \texttt{crearGrafo}$), en donde cada una de las aristas representan a las vallas, y los nodos son los extremos de estas vallas. Adem\'as, al crear el grafo, las vallas que tienen una altura menor a lo que saltan las langostas son eliminadas. Esto es porque una superficie esta resguardada solo si esta encerrada por vallas con una altura mayor o igual a lo que saltan las langostas, y por lo tanto, si la valla tiene una altura menor, podemos ignorarla. Para guardarnos el grafo usamos la estructura HashMap de Java, en donde las claves son las coordenadas (los nodos del grafo, es decir, los extremos de las vallas), y el significado es un objeto de la clase Vallas, el cual posee como atributo  la coordenada que comparten entre si las vallas y un ArrayList de objetos de la clase Valla, la cual contiene 2 pares de coordenadas para sus respectivos extremos y su altura. Notar que cada instancia de la clase Vallas usada para la resoluci\'on del problema va a tener a lo sumo 4 vallas en el arreglo (una valla al este del nodo, otra valla al norte del nodo, otra valla al sur del nodo, y otra valla al oeste) 

\vspace{0.5cm}

Una vez creado el grafo, lo primero que hacemos es eliminar las vallas que estamos seguros que no pertenecen a un ciclo ($\texttt{eliminarVallasFueraDeCiclos}$). \'Estas son las vallas que no estan conectadas a ninguna valla, o que est\'an conectadas a solamente una valla. Es decir, cada nodo que tiene 1 s\'olo significado, eliminamos el nodo del diccionario, y eliminamos la valla correspondiente al significado del otro extremo de la valla. Esta funci\'on se implementa f\'acilmente, primero ordenamos los significados en orden creciente con respecto a la cantidad de vallas que tenga, luego iteramos por cada una y , si tiene 0 o 1 valla hacemos la dicha eliminaci\'on en el grafo. Si aplicaramos este procedimiento al ejemplo del ``HOLA'', despues de recorrer todos los nodos que tienen 1 valla, el grafo nos queda de la siguiente forma (las vallas en marr\'on son eliminadas, como as\'i sus respectivos nodos marcados con una ``cruz''):

\vspace{0.5cm}

\begin{tikzpicture}
\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-2,1) {};

\draw[brown] plot[mark=x] coordinates{(1,1) (1,2) (1,3)};
\draw[brown] plot[mark=x] coordinates{(2,1) (2,2) (2,3)};
\draw[blue] plot[mark=ball] coordinates{(1,2) (2,2)};
\draw[blue] plot[mark=ball] coordinates{(3,3) (3,1) (4,1) (4,3) (3,3)};
\draw plot[mark=ball] coordinates{(5,1)};
\draw[brown] plot coordinates{(5,3) (5,1) (6,1)};
\draw[brown] plot[mark=x] coordinates{(5,3)};
\draw[brown] plot[mark=x] coordinates{(6,1)};
\draw[brown] plot[mark=x] coordinates{(7,1) (7,2)};
\draw[brown] plot[mark=x] coordinates{(8,1) (8,2)};
\draw[blue] plot[mark=ball] coordinates{(7,3) (7,2) (8,2) (8,3) (7,3)};
\end{tikzpicture}

\vspace{0.5cm}

De esta forma, los nodos correspondientes a la valla horizontal del medio de la H, y el nodo del extremo izquierdo de la valla inferior de la L que originalmente ten\'ian 3 y 2 vallas respectivamente, quedan con 1 y 0 vallas respectivamente. Como los nodos estaban ordenados por la cantidad de vallas que ten\'ian como significado, cuando el algoritmo itere los nodos que ten\'ian 2 significados originalmente, va a borrar el nodo restante de la L, y cuando itere los nodos que originalmente ten\'ian 3 nodos, va a borrar los nodos restantes de la H, quedando \'unicamente los 2 ciclos que es lo que quer\'iamos:

\vspace{0.5cm}

\begin{tikzpicture}

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-2,1) {};

\draw[brown] plot[mark=x] coordinates{(1,2) (2,2)};
\draw[blue] plot[mark=ball] coordinates{(3,3) (3,1) (4,1) (4,3) (3,3)};
\draw[brown] plot[mark=x] coordinates{(5,1)};
\draw[blue] plot[mark=ball] coordinates{(7,3) (7,2) (8,2) (8,3) (7,3)};
\end{tikzpicture}

\vspace{0.5cm}

Originalmente intu\'iamos que este procedimiento nos dejaba siempre con vallas pertenecientes a ciclos, por lo que en este punto seguimos desarrollando nuestro algoritmo pero pensando ahora en c\'omo buscar el ciclo que ``engloba'' a los dem\'as subciclos. Posteriormente, al seguir estudiando distintos grafos para cuando est\'abamos desarrollando la parte final del algoritmo, nos dimos cuenta que esto no era del todo as\'i y que de todas formas pod\'iamos seguir teniendo vallas no pertenecientes a ciclos como veremos mas adelante. Entonces, una vez que eliminamos esas vallas molestas, nos queremos quedar con nuestro ciclo general. Veamos con un ejemplo a que nos refer\'imos con el ciclo general, o el ciclo que engloba. Si nuestro grafo queda de la siguiente forma:

\vspace{0.5cm}

\begin{tikzpicture}

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (1,3) {};

\draw plot coordinates{(7,2) (7,6) (5,6) (5,4) (3,4) (3,6) (4,6) (4,7) (12,7) (12,3) (15,3) (15,2) (7,2)};
\draw plot coordinates{(9,4) (9,5) (10,5) (10,4) (9,4)};
\draw plot coordinates{(4,4) (4,5) (3,5) (5,5)};
\draw plot coordinates{(4,6) (5,6)};
\draw plot coordinates{(12,2) (12,3) (8,3) (8,7)};
\draw plot coordinates{(7,6) (11,6) (11,5) (12,5)};
\end{tikzpicture}

\vspace{0.5cm}

Lo que nosotros quisi\'eramos obtener es la siguiente figura a la cual s\'olo restar\'ia hallarle la superficie:

\vspace{0.5cm}

\begin{tikzpicture}

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (1,3) {};

\draw plot coordinates{(7,2) (7,6) (5,6) (5,4) (3,4) (3,6) (4,6) (4,7) (12,7) (12,3) (15,3) (15,2) (7,2)};
\end{tikzpicture}

\vspace{0.5cm}

Para realizar esto, nuestro algoritmo (funci\'on $\texttt{obtenerContornoCiclo}$) hace lo siguiente:
\begin{itemize}
\item Empieza por el nodo m\'as cercano al origen
\item Como es la valla m\'as cercana al origen, s\'i o s\'i tiene una valla que va al norte y otra al este (recordemos que era un ciclo, por lo tanto el nodo s\'i o s\' tiene que tener 2 vallas), ya que si no fuera as\'i y una de las vallas fuera al sur o al oeste del nodo, el otro extremo de la valla estar\'ia m\'as cercana al origen, y por lo tanto, el nodo por el cual hab\'ia empezado no era el m\'as cercano al origen, lo cual es absurdo.
\item Tomo la valla al norte, la guardo en una lista de vallas llamada ``recorrido'', y tomo el otro extremo de la valla como el nuevo nodo.
\item En este punto el algoritmo entra en un ciclo en donde, mientras que no se haya formado un ciclo (es decir, termina si la longitud del recorrido es mayor que 3, y que la ante-\'ultima valla del recorrido sea igual a la primera, y la ultima valla sea igual a la 2da..originalmente era s\'olo si la \'ultima valla era igual a la primera, pero despu\'es nos dimos cuenta que con eso s\'olo no bastaba como veremos m\'as adelante), el ciclo hace lo siguiente:
\begin{itemize}
\item Si ven\'ia en sentido norte, entonces intento ir para el oeste. En caso de que no haya valla al oeste del nuevo nodo, intento ir al norte. Por ultimo, en caso de que no haya valla al norte, voy al este. Recordemos que como estamos en un ciclo, alguno de los 3 casos se tiene que dar, ya que el nodo tiene que tener al menos 2 vallas.
\item Si ven\'ia en sentido oeste, entonces intento ir para el sur. En caso de que no haya valla al sur del nuevo nodo, intento ir al oeste. Por \'ultimo, en caso de que no haya valla al oeste, voy al norte.
\item Si ven\'ia en sentido sur, entonces intento ir al este. En caso de que no haya valla al este del nuevo nodo, intento seguir por el sur. Por \'ultimo, en caso de que no haya valla al sur, tomo la valla al oeste.
\item Si ven\'ia en sentido este, entonces intento ir al norte. En caso de que no haya valla al norte del nuevo nodo, intento ir al este. Por \'ultimo, en caso de que no haya valla al norte, voy al sur.
\item Me guardo la valla elegida en el recorrido, y tomo el otro extremo de la valla como el nuevo nodo.
\end{itemize}
\item Devolvemos la lista de vallas ``recorrido''
\end{itemize}

\vspace{0.5cm}

Y de esta forma obtenemos el contorno del ciclo ``general'' que quer\'iamos y s\'olo restar\'ia hallar la superficie del ciclo. Notar que s\'olo recorremos las vallas del contorno del ciclo, y no las vallas que se encuentran adentro de la supericfie.
\\
En este punto fue en donde tuvimos nuestro primer problema. Supongamos que el grafo sean 2 figuras unidas por una \'unica valla, como el de la siguiente figura:

\vspace{0.5cm}

\begin{tikzpicture}

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-1,1) {};

\draw plot coordinates{(4,1) (4,2) (5,2) (5,1) (4,1) (7,1) (7,2) (6,2) (6,1)};
\end{tikzpicture}

\vspace{0.5cm}

Ninguna valla es eliminada por el algoritmo de $\texttt{eliminarVallasFueraDeCiclos}$ ya que ning\'un nodo tiene 1 o 2 vallas, y por lo tanto la figura queda igual (en este punto fue que vimos que lo que intu\'iamos en un principio de que filtr\'abamos todas las vallas fuera de ciclos era err\'oneo). A\'un m\'as, una vez llamada a la funci\'on que obtiene el ciclo general, obtendr\'iamos las mismas vallas del grafo en la variable recorrido obtenida como resultado del algoritmo, pero con la valla que une 
ambos rect\'angulos 2 veces en el recorrido (una vez la obtendr\'iamos cuando va del cuadrado de la izquierda, al cuadrado de la derecha, y la misma valla cuando vuelve, del cuadrado de la derecha al cuadrado de la izquierda). Pero nosotros quer\'iamos obtener cada ciclo para luego, por cada ciclo, llamar a una funci\'on que halle 
la superficie del ciclo, por lo que en este caso particular, nos gustaria obtener los 2 ciclos por separado. Para esto, una vez que hallamos el recorrido, llamamos a una funci\'on que nos separa los ciclos que est\'an pegados por vallas. Esta funci\'on recibe una lista de vallas que es el recorrido obtenido con el algoritmo anterior (funci\'on $\texttt{subdividir\_figuras\_pegadas\_por\_aristas}$). Esta funci\'on hace lo siguiente:

Por cada valla en el recorrido pasado por parametro, miramos si \'esta se repite luego en el recorrido nuevamente. Si una valla se repite, entonces, se crean 2 nuevos recorridos, una que contiene todas las vallas hasta la posici\'on en donde estaba la primera aparici\'on de la valla que se repite, y todas las vallas que estaban despu\'es de la 2da aparici\'on de la valla que se repite, y el otro recorrido va a tener todas las vallas que estaban en el recorrido desde la primera aparici\'on de la valla, hasta la 2da aparici\'on de la valla. Luego, llamamos recursivamente a la funci\'on con los 2 nuevos recorridos obtenidos (es decir, cada una de las figuras que est\'an separadas por esa valla que antes las un\'ia..) en busca de nuevas figuras ``pegadas'' por otra valla.

\vspace{0.5cm}


Notar que un ciclo no puede quedar pegado a otro ciclo por una valla en su totalidad, en vez de por sus extremos. Es decir, no puede ocurrir lo siguiente:

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-6,1) {};

\node[mynodestyle] (v1) at (0,1) {};
\node[mynodestyle] (v2) at (0,-2) {};
\node[mynodestyle] (v3) at (3,1) {};
\node[mynodestyle] (v4) at (3,0) {};
\node[mynodestyle] (v5) at (2,0) {};
\node[mynodestyle] (v6) at (2,-1) {};
\node[mynodestyle] (v7) at (3,-1) {};
\node[mynodestyle] (v8) at (3,-2) {};
\node[mynodestyle] (v14) at (-2,1) {};
\node[mynodestyle] (v13) at (-2,2) {};
\node[mynodestyle] (v12) at (-3,2) {};
\node[mynodestyle] (v11) at (-3,0) {};
\node[mynodestyle] (v10) at (-2,0) {};
\node[mynodestyle] (v9) at (-2,-2) {};
\draw  (v1) edge[blue] (v2);
\draw  (v1) edge (v3);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v5) edge (v6);
\draw  (v6) edge (v7);
\draw  (v7) edge (v8);
\draw  (v8) edge (v2);
\draw  (v2) edge (v9);
\draw  (v9) edge (v10);
\draw  (v10) edge (v11);
\draw  (v11) edge (v12);
\draw  (v12) edge (v13);
\draw  (v13) edge (v14);
\draw  (v14) edge (v1);
\end{tikzpicture}

\vspace{0.5cm}

Por como recorre nuestro algoritmo el grafo, no podriamos tener esta situacion ya que la arista azul del medio no se encontraria en el recorrido hallado por el algoritmo.

\vspace{0.5cm}

Una vez hecho esto, nos dimos cuenta de que no bastaba en el algoritmo de $\texttt{obtenerContornoCiclo}$ del ciclo de pararlo cuando la \'ultima valla del recorrido era igual a la primera valla del recorrido, debido a que pod\'iamos tener el siguiente caso:

\vspace{0.5cm}

\begin{tikzpicture}
\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-2,1) {};

\draw plot coordinates{(2,1) (2,2) (3,2) (3,1) (1,1) (1,3) (8,3) (8,1) (6,1) (6,2) (7,2) (7,1)};
\end{tikzpicture}

\vspace{0.5cm}

Si aplicamos el algoritmo de recorrer el ciclo general, obtenemos el siguiente recorrido de vallas (las flechas marcan el sentido en el que el algoritmo recorrer\'ia el ciclo, y arriba de las vallas se indica como quedar\'ian asignadas en el arreglo ``recorrido'', que lo abreviamos con una ``r'' para mayor comodidad en el gr\'afico) 

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-8,-2) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v3) at (-4,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v6) at (-2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v4) at (-3,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v5) at (-3,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v7) at (-2,-1) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v1) at (-4,0) {};


\node [outer sep=0,inner sep=0,minimum size=0] (v8) at (0,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v10) at (0,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v11) at (1,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v9) at (1,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v12) at (2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v2) at (2,0) {};
\draw  (v1) edge[->,thick] node[above,sloped] {recorrido(2)} (v2);
\draw  (v1) edge[<-,thick] node[below,sloped] {r(1)} (v3);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v4) edge (v6);
\draw  (v6) edge (v7);
\draw  (v5) edge (v7);
\draw  (v8) edge[->,thick] node[above,sloped] {r(7)}(v9);
\draw  (v8) edge[<-,thick] node[below,sloped] {r(6)} (v10);
\draw  (v10) edge[<-,thick] node[below,sloped] {r(5)} (v11);
\draw  (v12) edge[->,thick] node[below,sloped] {r(4)}(v11);
\draw  (v9) edge[->,thick] node[above,sloped] {r(8)}(v11);
\draw  (v12) edge[<-,thick] node[below,sloped] {r(3)} (v2);
\end{tikzpicture}

\vspace{0.5cm}

Una vez que encuentra la valla n\'umero 8, como ven\'ia en sentido sur, primero intenta ir al este, como hay una valla, empieza a hacer el recorrido en sentido inverso:

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-8,-2) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v3) at (-4,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v6) at (-2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v4) at (-3,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v5) at (-3,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v7) at (-2,-1) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v1) at (-4,0) {};


\node [outer sep=0,inner sep=0,minimum size=0] (v8) at (0,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v10) at (0,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v11) at (1,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v9) at (1,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v12) at (2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v2) at (2,0) {};
\draw  (v1) edge[<-,thick] node[above,sloped] {recorrido(11)} (v2);
\draw  (v1) edge[->,thick] node[below,sloped] {r(12)} (v3);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v4) edge (v6);
\draw  (v6) edge (v7);
\draw  (v5) edge (v7);
\draw  (v8) edge (v9);
\draw  (v8) edge (v10);
\draw  (v10) edge (v11);
\draw  (v12) edge[<-,thick] node[below,sloped] {r(9)}(v11);
\draw  (v9) edge[->,thick] node[above,sloped] {r(8)}(v11);
\draw  (v12) edge[->,thick] node[below,sloped] {r(10)} (v2);
\end{tikzpicture}

\vspace{0.5cm}

De esta forma, como funcionaba nuestro algoritmo originalmente, que paraba cuando la \'ultima valla encontrada era igual a la primera valla, en este momento parar\'ia, y por lo tanto el recorrido obtenido contendr\'ia las siguientes vallas:

\vspace{0.5cm}

\begin{tikzpicture}
\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-2,1) {};

\draw plot coordinates{(1,1) (1,3) (8,3) (8,1) (6,1) (6,2) (7,2) (7,1)};
\end{tikzpicture}

\vspace{0.5cm}

Por lo que, al cuadrado de la izquierda ni lo estar\'iamos teniendo en cuenta, y el algoritmo final nos estar\'ia dando una superficie err\'onea. Por esta raz\'on, es necesario preguntar si hemos vuelto a pasar por la 1ra valla, y la 2da valla en el mismo orden. De esta forma, el algoritmo no para, y sigue hasta que halla el siguiente cuadrado, una vez que recorre el cuadrado, vuelve a pasar por la 1era valla, y seguidamente, por la 2da valla del recorrido nuevamente, por lo que recien ah\'i termina obteniendo en la variable recorrido las vallas deseadas:

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-8,-2) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v3) at (-4,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v6) at (-2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v4) at (-3,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v5) at (-3,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v7) at (-2,-1) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v1) at (-4,0) {};


\node [outer sep=0,inner sep=0,minimum size=0] (v8) at (0,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v10) at (0,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v11) at (1,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v9) at (1,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v12) at (2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v2) at (2,0) {};
\draw  (v1) edge (v2);
\draw  (v1) edge[->,thick] node[below,sloped] {r(12)} (v3);
\draw  (v3) edge[->,thick] node[below,sloped] {r(13)} (v4);%desde aca
\draw  (v4) edge[->,thick] node[above,sloped] {r(14)} (v5);
\draw  (v4) edge[<-,thick] node[below,sloped] {r(17)} (v6);
\draw  (v6) edge[<-,thick] node[below,sloped] {r(16)} (v7);
\draw  (v5) edge[->,thick] node[above,sloped] {r(15)} (v7);
\draw  (v8) edge (v9);
\draw  (v8) edge (v10);
\draw  (v10) edge (v11);%hasta aca
\draw  (v12) edge (v11);
\draw  (v9) edge (v11);
\draw  (v12) edge (v2);
\end{tikzpicture}

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-8,-2) {};

\node [mynodestyle] (v3) at (-4,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v6) at (-2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v4) at (-3,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v5) at (-3,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v7) at (-2,-1) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v1) at (-4,0) {};


\node [outer sep=0,inner sep=0,minimum size=0] (v8) at (0,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v10) at (0,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v11) at (1,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v9) at (1,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v12) at (2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v2) at (2,0) {};
\draw  (v1) edge[->,thick] node[above,sloped] {r(20)} (v2);
\draw  (v1) edge[<-,thick] node[below,sloped] {r(19)} (v3);
\draw  (v3) edge[<-,thick] node[below,sloped] {r(18)} (v4);%desde aca
\draw  (v4) edge (v5);
\draw  (v4) edge[<-,thick] node[below,sloped] {r(17)} (v6);
\draw  (v6) edge (v7);
\draw  (v5) edge (v7);
\draw  (v8) edge (v9);
\draw  (v8) edge (v10);
\draw  (v10) edge (v11);%hasta aca
\draw  (v12) edge (v11);
\draw  (v9) edge (v11);
\draw  (v12) edge (v2);
\end{tikzpicture}

\vspace{0.5cm}

 Luego si aplicamos el algoritmo que divide las superficies pegadas por vallas, obtenemos los 2 cuadrados como dese\'abamos. Y aca nos vimos que lo podiamos hacer un poco mas eficiente a nuestro algoritmo que dividia superficies pegadas por vallas. Veamos como fue esta mejora. Una vez que encontrabamos una valla que se repetia, miramos cuantas vallas se repitieron hasta ese momento. Entonces, en el ejemplo ultimo, tenemos lo siguiente:

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]
\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-8,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v3) at (-4,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v6) at (-2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v4) at (-3,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v5) at (-3,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v7) at (-2,-1) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v1) at (-4,0) {};


\node [outer sep=0,inner sep=0,minimum size=0] (v8) at (0,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v10) at (0,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v11) at (1,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v9) at (1,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v12) at (2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v2) at (2,0) {};
\draw  (v1) edge node[above,sloped] {recorrido(2)} (v2);
\draw  (v1) edge node[below,sloped] {r(1)} (v3);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v4) edge (v6);
\draw  (v6) edge (v7);
\draw  (v5) edge (v7);
\draw  (v8) edge node[above,sloped] {r(7)}(v9);
\draw  (v8) edge node[below,sloped] {r(6)} (v10);
\draw  (v10) edge node[below,sloped] {r(5)} (v11);
\draw  (v12) edge node[below,sloped] {r(4)}(v11);
\draw  (v9) edge node[above,sloped] {r(8)}(v11);
\draw  (v12) edge node[below,sloped] {r(3)} (v2);
\end{tikzpicture}

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [outer sep=0,inner sep=0,minimum size=0] (v20) at (-8,-2) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v3) at (-4,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v6) at (-2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v4) at (-3,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v5) at (-3,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v7) at (-2,-1) {};

\node [outer sep=0,inner sep=0,minimum size=0] (v1) at (-4,0) {};


\node [outer sep=0,inner sep=0,minimum size=0] (v8) at (0,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v10) at (0,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v11) at (1,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v9) at (1,-1) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v12) at (2,-2) {};
\node [outer sep=0,inner sep=0,minimum size=0] (v2) at (2,0) {};
\draw  (v1) edge node[above,sloped] {recorrido(11)} (v2);
\draw  (v1) edge node[below,sloped] {r(12)} (v3);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v4) edge (v6);
\draw  (v6) edge (v7);
\draw  (v5) edge (v7);
\draw  (v8) edge (v9);
\draw  (v8) edge (v10);
\draw  (v10) edge (v11);
\draw  (v12) edge node[below,sloped] {r(9)}(v11);
\draw  (v9) edge node[above,sloped] {r(8)}(v11);
\draw  (v12) edge node[below,sloped] {r(10)} (v2);
\end{tikzpicture}

\vspace{0.5cm}

El algoritmo empieza mirando r(1) (guarda a 1 en la variable i), y se fija si existe una valla que este despues en el recorrido que sea igual a r(1). Como r(12) = r(1), deja de buscar, se guarda el valor 12 en una variable (variable j), y divide los ciclos como habiamos explicado anteriormente. Ahora, la mejora hace lo siguiente: Miramos hasta donde se repetian las vallas. Como r(11) = (2), r(10) = r(3), r(9) = r(4), pero r(8) no es igual a r(5), no busca mas y nos guardamos hasta que valores se repetian (en ii nos guardamos 4, y en jj nos guardamos 9). Entonces, las vallas que estan entre i y ii, y las vallas que estan entre j y jj, nos gustaria ignorarlas ya que no pertenecen a un ciclo porque se repiten. Por lo tanto, los nuevos recorridos quedan divididos de la siguiente forma: Un recorrido va desde 0 hasta i-1, y de j+1 hasta el ultimo elemento, y el otro recorrido queda desde ii+1 hasta jj-1. De esta forma, en estos casos que las vallas se repiten varias veces una seguida de la otra, las llamadas recursivas tendran una cantidad de vallas menor a recorrer.

\vspace{0.5cm}

Hasta este momento entonces tenemos distintos ciclos, en los que cada ciclo los representamos como una lista de vallas, cada una unida por un v\'ertice con la siguiente (la primera valla est\'a conectada a la 2da valla, la 2da valla est\'a conectada con la 3era valla (y con la 1era, claro est\'a)..y as\'i sucesivamente). Llegados a este punto, tuvimos que pensar en un algoritmo que, dado cualquier ciclo obtenido con la serie de algoritmos anteriores, y con las caracter\'isticas del problema, nos halle la superficie. Para lograr esta \'ultima parte del algoritmo dimos much\'isimas vueltas y hasta programamos un algoritmo inicialmente que s\'olo funcionaba con un subgrupo particular de circuitos. De esta forma, llegamos a la conclusi\'on de que lo m\'as fiable era intentar subdividir la figura en rect\'angulos, y hallar la superficie de cada rect\'angulo que la compon\'ia, la cual es una figura que sabemos calcular y es f\'acil de hacerlo. Por este motivo, antes de subdividir al ciclo en rect\'angulos, primero lo que hacemos es unir todas las vallas unidas por un v\'ertice que van en el mismo sentido. Es decir, si tenemos 2 vallas consecutivas en la lista de vallas del recorrido que son horizontales, o 2 vallas que son verticales, entonces las unimos en una sola valla. De esta forma, si tenemos un recorrido de tama\~no 4, como sabemos que esstamos analizando un circuito y tiene 4 vallas, por lo tanto, tiene que ser un rect\'angulo, y con lo cual, s\'olo resta hallar la superficie calculando la base y multiplic\'andola por la altura. Ahora, si el recorrido queda con un tama\~no mayor a 4 vallas, quiere decir que no es un rect\'angulo, y que hay que dividirlo. De esta forma, pasamos al algoritmo siguiente que subdivide un ciclo obtenido hasta el momento, en rect\'angulos (funci\'on $\texttt{dividirEnRectangulos}$).
\\
Para realizar esto, despu\'es de estudiar muchos grafos, nos dimos cuenta que lo pod\'iamos hacer, mientras vamos recorriendo el ciclo, s\'olo extendiendo ciertas vallas: 

\begin{itemize}
\item Si vengo en sentido norte, y la valla siguiente va en sentido este, entonces, extendemos la valla al norte hasta que se interseque con alguna valla al norte. Luego, creamos los 2 ciclos que quedan formados, y llamamos recursivamente a las 2 figuras que quedan divididas.
\end{itemize}


\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node[mynodestyle] (v16) at (-5,0) {};
\node[mynodestyle] (v5) at (-2,0) {};
\node[mynodestyle] (v4) at (-1,0) {};
\node[mynodestyle] (v6) at (-2,1) {};
\node[mynodestyle] (v1) at (-3,1) {};
\node[mynodestyle] (v2) at (-3,2) {};
\node[mynodestyle] (v3) at (-1,2) {};
\node[mynodestyle] (v7) at (-2,2) {};
\draw  (v1) edge (v2);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v5) edge[->,thick] (v6);
\draw  (v1) edge[<-,thick] (v6);
\draw  (v6) edge[dashed] (v7);
\draw  (v2) edge (v7);
\draw  (v7) edge (v3);
\draw [->,very thick] (1,1) -- +(1,0);
\node [mynodestyle] (v11) at (4,2) {};
\node [mynodestyle] (v8) at (3,2) {};
\node [mynodestyle] (v9) at (3,1) {};
\node [mynodestyle] (v10) at (4,1) {};
\draw  (v8) edge (v9);
\draw  (v10) edge (v11);
\draw  (v9) edge (v10);
\draw  (v8) edge (v11);
\node [mynodestyle] (v12) at (5,2) {};
\node [mynodestyle] (v13) at (5,0) {};
\node [mynodestyle] (v14) at (6,2) {};
\node [mynodestyle] (v15) at (6,0) {};
\draw  (v12) edge (v13);
\draw  (v13) edge (v15);
\draw  (v15) edge (v14);
\draw  (v14) edge (v12);
\end{tikzpicture}

\begin{itemize}
\item Si vengo en sentido oeste, y la valla siguiente va en sentido sur, entonces, extendemos la valla al oeste hasta que se interseque con alguna valla. Luego, creamos los 2 ciclos que quedan formados, y llamamos recursivamente a las 2 figuras que quedan divididas.
\end{itemize}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]


\node [mynodestyle] at (-6,1) {};
\node [mynodestyle] (v2) at (-1,1) {};
\node [mynodestyle] (v1) at (-1,-1) {};

\node [mynodestyle] (v5) at (0,0) {};
\node [mynodestyle] (v6) at (0,-1) {};
\node [mynodestyle] (v4) at (1,0) {};
\node [mynodestyle] (v3) at (1,1) {};
\node [mynodestyle] (v7) at (-1,0) {};

\draw  (v1) edge[->] (v2);
\draw  (v2) edge[->] (v3);
\draw  (v3) edge[->] (v4);
\draw  (v4) edge[->] (v5);
\draw  (v5) edge[->] (v6);
\draw  (v6) edge (v1);
\draw  (v7) edge[dashed] (v5);

\end{tikzpicture}

\begin{itemize}
\item Si vengo en sentido este, y la valla siguiente va en sentido norte, entonces, extendemos la valla al eeste hasta que se interseque con alguna valla. Luego, creamos los 2 ciclos que quedan formados, y llamamos recursivamente a las 2 figuras que quedan divididas.
\end{itemize}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]


\node [mynodestyle] at (-6,1) {};
\node [mynodestyle] (v2) at (-1,1) {};
\node [mynodestyle] (v5) at (0,0) {};
\node [mynodestyle] (v4) at (1,0) {};
\node [mynodestyle] (v3) at (1,1) {};
\node [mynodestyle] (v7) at (-1,0) {};

\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v7) edge (v5);

\node [mynodestyle] (v1) at (0,1) {};
\node [mynodestyle] (v6) at (0,2) {};
\node [mynodestyle] (v8) at (1,2) {};
\draw  (v7) edge[->] (v2);
\draw  (v2) edge[->] (v1);
\draw  (v1) edge[->] (v6);
\draw  (v6) edge (v8);
\draw  (v8) edge (v3);
\draw  (v1) edge[dashed] (v3);
\end{tikzpicture}

\begin{itemize}
\item Si vengo en sentido sur, y la valla siguiente va en sentido este, entonces, extendemos la valla al sur hasta que se interseque con alguna valla. Luego, creamos los 2 ciclos que quedan formados, y llamamos recursivamente a las 2 figuras que quedan divididas.
\end{itemize}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] at (-6,1) {};
\node [mynodestyle] (v2) at (-1,1) {};
\node [mynodestyle] (v4) at (1,0) {};
\node [mynodestyle] (v3) at (1,1) {};
\node [mynodestyle] (v5) at (-1,-1) {};
\node [mynodestyle] (v1) at (2,0) {};
\node [mynodestyle] (v6) at (2,-1) {};

\draw  (v5) edge[->] (v2);
\draw  (v2) edge[->] (v3);
\draw  (v3) edge[->] (v4);
\draw  (v4) edge[->] (v1);
\draw  (v1) edge (v6);
\draw  (v6) edge (v5);
\node [mynodestyle] (v7) at (1,-1) {};
\draw  (v4) edge[dashed] (v7);
\end{tikzpicture}

\vspace{0.5cm}

Esta idea, que originalmente pens\'abamos que no iba a ser muy dif\'icil de implementar, tiene varios detalles que nos fueron complicando a medidia que lo implement\'abamos. Originalmente, esos 4 casos b\'asicos se implementar\'ian de la siguiente forma:

\begin{itemize}
\item En cada caso, si entramos a alguno de los casos anteriores, nos guardamos el \'indice de la valla a extender (llamemos a este \'indice ``i'') y buscamos la valla m\'as cercana al norte, oeste, este, o sur (respectivamente). Supongamos que esta valla se encontraba en la posici\'on j del arreglo recorrido.
\item Dividimos la valla encontrada, teniendo en la posici\'on j la primera parte de la valla hasta que se "interseca" con la extensi\'on, y en j+1 vamos a tener la 2da parte de la valla.
\item Creamos una nueva valla que va desde el extremo a extender de la valla en la posici\'on i, hasta donde se encuentra la valla de la posici\'on j. Llam\'emosla ``nueva\_valla''. Adem\'as, creamos otra valla que es la valla extendida (``valla\_extendida'')
\item Eliminamos la valla vieja que se encontraba en la posici\'on i, y agregamos en la misma posici\'on valla ``valla\_extendida''. En la posici\'on siguiente (osea, posici\'on i+1) agregamos la otra valla creada, es decir, ``nueva\_valla''. De esta forma, nos van a quedar desde la posici\'on 0 hasta la posici\'on i, m\'as las vallas que se encuentran desde la posici\'on j+1 (j+2 en realidad ya que ahora el j se nos corri\'o un lugar al haber insertado una valla en la primera parte del arreglo) hasta el final del recorrido las vallas correspondientes a una de las divisiones. Desde la posici\'on i+1 hasta la posicion j+1, las vallas correspondientes a la otra divisi\'on.
\end{itemize}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v2) at (-3,1) {};
\node [mynodestyle] (v5) at (0,0) {};
\node [mynodestyle] (v4) at (2,0) {};
\node [mynodestyle] (v3) at (2,1) {};
\node [mynodestyle] (v7) at (-3,0) {};
\node [mynodestyle] (v1) at (0,1) {};
\node [mynodestyle] (v6) at (0,3) {};
\node [mynodestyle] (v8) at (2,3) {};
\node [mynodestyle] (v9) at (5,1) {};
\node [mynodestyle] (v10) at (8,1) {};
\node [mynodestyle] (v11) at (8,3) {};
\node [mynodestyle] (v12) at (10,3) {};
\node [mynodestyle] (v13) at (10,1) {};
\node [mynodestyle] (v14) at (10,0) {};
\node [mynodestyle] (v15) at (5,0) {};

\draw [->,very thick] (3,1) -- +(1,0);

\draw  (v3) edge node[above,sloped] {r(5)} (v4);
\draw  (v4) edge (v5);
\draw  (v7) edge (v5);
\draw  (v7) edge[->] node[above,sloped] {r(0)} (v2);
\draw  (v2) edge[->] node[above,sloped] {r(i = 1)} (v1);
\draw  (v1) edge[->] node[above,sloped] {r(2)} (v6);
\draw  (v6) edge (v8);
\draw  (v8) edge node[above,sloped] {r(j = 4)} (v3);
\draw  (v1) edge[dashed] (v3);

\draw (v9) edge node[below,sloped] {r(i = 1)} (v13);
\draw (v10) edge node[above,sloped] {r(i+1 = 2)} (v13);
\draw (v10) edge node[above,sloped] {r(3)} (v11);
\draw (v11) edge node[above,sloped] {r(j = 4)} (v12);
\draw (v12) edge node[above,sloped] {r(j+1 = 5)} (v13);
\draw (v13) edge node[above,sloped] {r(6)} (v14);
\draw (v14) edge (v15);
\draw (v15) edge node[above,sloped] {r(0)} (v9);


\end{tikzpicture}

\vspace{0.5cm}

La valla que llamamos ``valla\_extendida'' la extendemos por el hecho de que no queremos que tengamos vallas contiguas en el mismo sentido. Si no la uni\'eramos en una misma valla, en el ejemplo, nos quedar\'ia un recorrido con 5 vallas en vez de 4 para el nuevo ciclo, y como hab\'iamos indicado anteriormente, nuestro algoritmo deja de subdividir s\'olo cuando el ciclo tiene longitud 4 (es nuestra forma de asegurarnos de que llegamos a un rect\'angulo). Ahora, este algoritmo funciona si s\'olo si la valla buscada se encuentra en una posici\'on posterior con respecto a la valla que ten\'iamos que extender (es decir, si i es menor que j). Por esta raz\'on, tenemos que considerar el caso en que la valla hallada est\'a en una posici\'on menor que la que ten\'iamos que extender (un ejemplo de este caso podr\'ia ser la figura del caso ``Si vengo en sentido oeste..'' ya que la valla a encontrar en ese caso ser\'ia la 1er valla del recorrido). Por esta raz\'on, para la subdivision de los ciclos tenemos 2 versiones, una para cada caso, llamadas $\texttt{subdividirCicloAntes}$ y $\texttt{subdividirCicloDespues}$. En este otro caso, el algoritmo quedar\'ia as\'i:

\begin{itemize}
\item En cada caso, si entramos a alguno de los casos anteriores, nos guardamos el \'indice de la valla a extender (llamemos a este \'indice ``i'') y buscamos la valla m\'as cercana al norte, oeste, este, o sur (respectivamente). Supongamos que esta valla se encontraba en la posici\'on j del arreglo recorrido.
\item Dividimos la valla encontrada, teniendo en la posici\'on j la primera parte de la valla hasta que se "interseca" con la extensi\'on, y en j+1 vamos a tener la 2da parte de la valla.
\item Creamos una nueva valla que va desde el extremo a extender de la valla en la posici\'on i, hasta donde se encuentra la valla de la posici\'on j. Llam\'esmosla ``nueva\_valla''. Adem\'as, creamos otra valla que es la valla extendida (``valla\_extendida'')
\item Eliminamos la valla vieja que se encontraba en la posici\'on i. En la \textbf{posici\'on de la valla que hab\'iamos dividido, o sea la posici\'on j, ahora como agregamos una valla m\'as en la primera parte del arreglo quedar\'ia en realidad en la posici\'on j+1,  agregamos la valla creada, es decir, ``nueva\_valla''. En la posici\'on siguiente, o sea, posici\'on j+2, agregamos ``valla\_extendida''. De esta forma, nos van a quedar desde la posici\'on 0 hasta la posici\'on j+1, m\'as las vallas que se encuentran desde la posici\'on  i+2 (esto es porque al agregar vallas en el medio del arreglo el \'indice qued\'o ``corrido'') hasta el final del recorrido las vallas correspondientes a una de las divisiones. Desde la posici\'on j+2 hasta la posici\'on i+1, las vallas correspondientes a la otra divisi\'on.}
\end{itemize}


Y ac\'a se nos empezaron a complicar un poco m\'as las cosas cuando empezamos a ver con esto no cubr\'iamos todos los diferentes tipos de ciclos posibles. Tenemos casos en donde la valla que extendemos no ``divide'' a la mitad a la valla con la cual interseca. Veamos estos casos que nos faltan contemplar con dos ejemplos, que entran en el caso de cuando queremos extender una valla en el sentido sur (para los dem\'as sentidos son an\'alogos):


\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v18) at (-1,-2) {Caso B};
\node [mynodestyle] (v19) at (-6,-2) {Caso A};
\node [mynodestyle] (v2) at (-2,2) {};
\node [mynodestyle] (v3) at (0,2) {};
\node [mynodestyle] (v4) at (0,1) {};
\node [mynodestyle] (v5) at (1,1) {};
\node [mynodestyle] (v6) at (1,0) {};
\node [mynodestyle] (v7) at (0,0) {};
\node [mynodestyle] (v8) at (0,-1) {};
\node [mynodestyle] (v1) at (-2,-1) {};

\draw  (v1) edge[->]  node[above,sloped] {r(0)} (v2);
\draw  (v2) edge[->]  node[above,sloped] {r(1)} (v3);
\draw  (v3) edge[->]  node[above,sloped] {r(2)} (v4);
\draw  (v4) edge (v5);
\draw  (v5) edge (v6);
\draw  (v6) edge (v7);
\draw  (v7) edge (v8);
\draw  (v8) edge (v1);
\draw (v4) edge[dashed] (v7);

\node [mynodestyle] (v17) at (-11,-1) {};
\node [mynodestyle] (v9) at (-6,-1) {};
\node [mynodestyle] (v10) at (-6,0) {};
\node [mynodestyle] (v11) at (-7,0) {};
\node [mynodestyle] (v12) at (-7,2) {};
\node [mynodestyle] (v13) at (-6,2) {};
\node [mynodestyle] (v14) at (-6,1) {};
\node [mynodestyle] (v15) at (-5,1) {};
\node [mynodestyle] (v16) at (-5,-1) {};

\draw  (v9) edge (v10);
\draw  (v10) edge (v11);
\draw  (v11) edge[->]  node[above,sloped] {r(0)} (v12);
\draw  (v12) edge[->]  node[above,sloped] {r(1)} (v13);
\draw  (v13) edge[->]  node[above,sloped] {r(2)} (v14);
\draw  (v14) edge (v15);
\draw  (v15) edge (v16);
\draw  (v16) edge (v9);
\draw  (v14) edge[dashed] (v10);

\end{tikzpicture}

\vspace{0.5cm}

En ambos casos, el procedimiento para dvidir los subciclos se pueden deducir an\'alogamente como lo hemos hecho para los casos anteriores. La diferencia, es que en estos casos, no hay divisi\'on de la valla encontrada al sur, y cambian las vallas que se crean para cada subciclo. Cuando en el procedimiento anterior ten\'iamos las vallas creadas ``valla\_extendida'' y ``nueva\_valla'', en el caso A vamos a tener 2 vallas extendidas (extendidas con la que hab\'iamos llamado anteriormente como ``nueva\_valla''), y en el caso B vamos a tener una valla ``doblemente'' extendida junto con la ``nueva\_valla'' para el otro ciclo.

 \vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v20) at (-1,-2) {Caso B};
\node [mynodestyle] (v21) at (-7,-2) {Caso A};
\node [mynodestyle] (v2) at (-3,2) {};
\node [mynodestyle] (v3) at (-1,2) {};
\node [mynodestyle] (v4) at (-1,1) {};
\node [mynodestyle] (v5) at (1,1) {};
\node [mynodestyle] (v6) at (1,0) {};
\node [mynodestyle] (v7) at (-1,0) {};
\node [mynodestyle] (v8) at (-1,-1) {};
\node [mynodestyle] (v1) at (-3,-1) {};
\node [mynodestyle] (v18) at (0,1) {};
\node [mynodestyle] (v19) at (0,0) {};

\draw  (v1) edge  (v2);
\draw  (v2) edge (v3);
\draw  (v3) edge  node[above,sloped] {doble\_extendida} (v8);
\draw  (v18) edge (v5);
\draw  (v5) edge (v6);
\draw  (v6) edge (v19);
\draw  (v7) edge (v8);
\draw  (v8) edge (v1);
\draw  (v19) edge node[above,sloped] {nueva\_valla}  (v18);

\node [mynodestyle] (v22) at (-11,-1) {};
\node [mynodestyle] (v9) at (-6,-1) {};
\node [mynodestyle] (v10) at (-7,0) {};
\node [mynodestyle] (v11) at (-8,0) {};
\node [mynodestyle] (v12) at (-8,2) {};
\node [mynodestyle] (v13) at (-7,2) {};
\node [mynodestyle] (v14) at (-7,1) {};
\node [mynodestyle] (v15) at (-5,1) {};
\node [mynodestyle] (v16) at (-5,-1) {};
\node [mynodestyle] (v17) at (-6,1) {};


\draw  (v10) edge (v11);
\draw  (v11) edge (v12);
\draw  (v12) edge (v13);
\draw  (v13) edge node[above,sloped] {extendida1} (v10);
\draw  (v17) edge (v15);
\draw  (v15) edge (v16);
\draw  (v16) edge (v9);
\draw  (v14) edge (v10);
\draw (v9) edge node[above,sloped] {extendida2} (v17);

\end{tikzpicture}

\vspace{0.5cm}

De esta forma, cubrimos todos los diferentes casos y obtenemos el algoritmo deseado que nos subdivide la figura en rect\'angulos. Todos los diferentes casos? No, todos los diferentes casos cuando necesitamos extender vallas para dividir figuras. Pero hay un caso m\'as que tenemos que considerar, en el cual no tenemos que extender vallas, sino que tenemos que dividir las figuras nada m\'as: cuando tenemos 2 figuras pegadas por un \'unico vertice. Ve\'amoslo con un ejemplo:

\vspace{0.5cm}

% 2 cuadrados pegados por 1 v\'ertice
\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v8) at (0,3) {};
\node [mynodestyle] (v1) at (5,2) {};
\node [mynodestyle] (v2) at (5,0) {};
\node [mynodestyle] (v3) at (7,2) {};
\node [mynodestyle] (v4) at (7,0) {};
\draw  (v1) edge (v3);
\draw  (v2) edge (v4);
\draw  (v2) edge (v1);
\draw  (v4) edge (v3);

\node [mynodestyle] (v5) at (9,0) {};
\node [mynodestyle] (v6) at (7,-2) {};
\node [mynodestyle] (v7) at (9,-2) {};
\draw  (v4) edge (v5);
\draw  (v6) edge (v7);
\draw  (v6) edge (v4);
\draw  (v7) edge (v5);

\end{tikzpicture}

\vspace{0.5cm}

Si recibimos esa superficie como entrada, nuestro algoritmo va a recorrerlo de la siguiente forma:

\vspace{0.5cm}

% 2 cuadrados pegados por 1 v\'ertice
\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v8) at (0,3) {};
\node [mynodestyle] (v1) at (5,2) {};
\node [mynodestyle] (v2) at (5,0) {};
\node [mynodestyle] (v3) at (7,2) {};
\node [mynodestyle] (v4) at (7,0) {};
\draw  (v1) edge[->]  node[above,sloped] {r(1)} (v3);
\draw  (v2) edge[<-] node[above,sloped] {r(7)} (v4);
\draw  (v2) edge[->] node[above,sloped] {r(0)} (v1);
\draw  (v4) edge[<-] node[above,sloped] {r(2)} (v3);

\node [mynodestyle] (v5) at (9,0) {};
\node [mynodestyle] (v6) at (7,-2) {};
\node [mynodestyle] (v7) at (9,-2) {};
\draw  (v4) edge[->] node[above,sloped] {r(3)} (v5);
\draw  (v6) edge[<-] node[above,sloped] {r(5)} (v7);
\draw  (v6) edge[->] node[above,sloped] {r(6)} (v4);
\draw  (v7) edge[<-] node[above,sloped] {r(4)} (v5);

\end{tikzpicture}

\vspace{0.5cm}

Aclaraci\'on: Al empezar nuestro algoritmo por el nodo m\'as cercano al origen, podr\'ia haber empezado por el nodo que conecta r(5) y r(6), ya que ese nodo y el nodo que conecta r(7) con r(0) est\'an a la misma distancia del origen. Pero supongamos que empieza por el otro nodo, tal cual se muestra en la figura. Cuando se llama a la funci\'on $\texttt{dividirEnRectangulos}$, y recorre la valla que se encuentra en la posici\'on 2 del recorrido, como ven\'ia en sentido sur y la valla siguiente va en sentido este, va a querer extender la valla al sur como hab\'iamos explicado anteriormente. Y ac\'a hay un problema, no hay nada que extender!. Por lo tanto, siempre antes de que extendamos una valla, tenemos que chequear que no estemos parados en un nodo en el cual tenemos 2 figuras unidas por ese nodo, y si lo estamos, separarlas. La funci\'on que se encarga de esto es sencilla, y se llama \texttt{hayFiguraPegadaPorVertice}. Recibe el recorrido, y la posible valla a extender, y nos devuelve el \'indice de la primera valla posterior a la primera valla siguiente a ella, que tiene uno de sus extremos en el mismo vertice o -1 si no hay una 3era valla conectada a ese v\'ertice. Es decir, en el ejemplo anterior, nos devolver\'ia el \'indice 6, que es la primera valla despu\'es de r(3) que tiene un extremo en el mismo nodo que r(2). Una vez obtenido el \'indice, solo restar separar los ciclos de manera directa.

\vspace{0.5cm}

De esta forma, terminamos dividiendo la figura en rect\'angulos y s\'olo resta calcular, para cada rect\'angulo que hallamos, su superficie. Por \'ultimo, nos falta aclarar que esto funciona para cada componente conexa. Por lo tanto, todo este algoritmo (desde que se llama a la funcion \texttt{obtenerContornoCiclo} hasta que hallamos la superficie de cada rectangulo que compone a la figura) esta contenido en un loop, que itera por todos los nodos del hashmap original (o sea, donde represent\'abamos al grafo original) y pregunta si el nodo ya se recorri\'o, o si est\'a adentro de la superficie de alg\'un recta\'ngulo que se hall\'o (esto \'ultimo es porque, como dijimos anteriormente, las vallas internas del ciclo no se recorren cuando se llama a \texttt{obtenerContornoCiclo}, y por lo tanto, los nodos internos tampoco se recorren).

\vspace{0.5cm}

Hay muchas funciones que nos salteamos de explicar c\'omo est\'an implementadas o programadas porque no creemos que valgan la pena explicar (mas que nada por que son f\'aciles de implementar y/o no tienen nada interesante que aclarar) y porque ya de por s\'i el informe nos estaba quedando algo largo =).


\vspace{1cm}


\subsubsection*{Complejidad}

\vspace{0.5cm}

Comencemos mirando nuestro primer algoritmo, que divide las vallas cada vez que hay una intersecci\'on entre vallas. Esta funci\'on es O(vallas$^{2}$) ya que por cada valla, se fija si hay otra valla que la interseque (lo cual, ver si una valla interseca a la otra lo podemos ver en O(1), y crear las nuevas vallas en caso de que as\'i sea, como a\~nadirlas, tambi\'en se hace en O(1)). Ahora, en este punto podr\'iamos tener un problema, ya que estamos cambiando la cantidad de vallas originales, y, si necesitamos recorrer las vallas, y la nueva cantidad de vallas es una potencia de la anterior, podriamos tener un problema y que nuestro algoritmo no quede con la complejidad que quer\'iamos. As\'i que veamos de qu\'e orden nos queda la cantidad de vallas una vez que las dividimos:

\vspace{0.5cm}

Como una valla es horizontal o vertical, las podemos dividir en 2 conjuntos disjuntos, donde la union forma todo el conjunto de vallas del problema. Ahora, supongamos que tenemos un numero par de vallas, y la mitad de las vallas son horizontales, y la otra mitad son verticales. El peor caso que puede pasar es que cada valla horizontal se interseca con cada una de las vallas verticales:

\vspace{0.5cm}

\colorlet{ellipse edge}{blue!50}
\tikzset{outline/.style={draw=ellipse edge, very thick}}

\begin{tikzpicture}

\draw[outline]  (-2,3) ellipse (3 and 4);
\draw[outline]  (7,3) ellipse (3 and 4);
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v1) at (-2,5) {$h_{1}$};
\node [mynodestyle] (v10) at (-2,1) {$h_{n/2}$};
\node (v7) at (-2,4) {.};
\node (v8) at (-2,3) {.};
\node (v9) at (-2,2) {.};
\node (v2) at (7,5) {$v_{1}$};
\node (v3) at (7,4) {.};
\node (v4) at (7,3) {.};
\node (v5) at (7,2) {.};
\node (v6) at (7,1) {$v_{n/2}$};

\draw[green]  (v1) edge (v2);
\draw[green]  (v1) edge (v4);
\draw[green]  (v1) edge (v6);
\draw[green]  (v10) edge (v2);
\draw[green]  (v10) edge (v4);
\draw[green]  (v10) edge (v6);
\draw[green]  (v8) edge (v2);
\draw[green]  (v8) edge (v4);
\draw[green]  (v6) edge (v8);

\node at (-2,8) {Vallas Horizontales};
\node at (7,8) {Vallas Verticales};
\end{tikzpicture}

\vspace{0.5cm}

De esta forma, tenemos $\frac{n}{2}$  $\cdot\frac{n}{2}$ = $\frac{n^{2}}{4}$ intersecciones. Si una valla se interseca con otra en un punto del medio de ambas vallas, entonces nuestro problema genera 2 vallas nuevas, por lo tanto, tenemos por cada intersecci\'on como mucho 2 vallas nuevas,es decir, tenemos $\frac{n^{2}}{4} \cdot 2$ = $\frac{n^{2}}{2}$ vallas nuevas. De esta manera, una vez que dividimos las vallas al inicio de nuestro algoritmo, si recorremos todas las vallas del grafo estamos en un orden del O($vallas^{2}$), lo cual es algo que nos complica. Pero veamos un poco m\'as en detalle cu\'ando se da este caso, con un ejemplo con 6 vallas, 3 horizontales y 3 verticales:

\vspace{0.5cm}

\vspace{0.5cm}


\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]
\tikzstyle{myedgestyle} = [blue,very thick]

\node [mynodestyle] (v21) at (-5,0) {};
\node [mynodestyle] (v13) at (0,0) {};
\node [ mynodestyle] (v14) at (1,0) {};
\node [mynodestyle] (v15) at (2,0) {};
\node [mynodestyle] (v20) at (0,1) {};
\node [mynodestyle] (v16) at (2,1) {};
\node [mynodestyle] (v19) at (0,2) {};
\node [mynodestyle] (v18) at (1,2) {};
\node [mynodestyle] (v17) at (2,2) {};
\node [mynodestyle] (v1) at (0,-1) {};
\node [mynodestyle] (v3) at (1,-1) {};
\node [mynodestyle] (v5) at (2,-1) {};
\node [mynodestyle] (v11) at (3,0) {};
\node [mynodestyle] (v9) at (3,1) {};
\node [mynodestyle] (v7) at (3,2) {};
\node [mynodestyle] (v8) at (-1,2) {};
\node [mynodestyle] (v10) at (-1,1) {};
\node [mynodestyle] (v12) at (-1,0) {};
\node [mynodestyle] (v2) at (0,3) {};
\node [mynodestyle] (v4) at (1,3) {};
\node [mynodestyle] (v6) at (2,3) {};

\draw  (v1) edge (v2);
\draw  (v3) edge (v4);
\draw  (v5) edge (v6);
\draw  (v7) edge (v8);
\draw  (v9) edge (v10);
\draw  (v11) edge (v12);
\draw [myedgestyle] (v1) edge (v13);
\draw [myedgestyle] (v3) edge (v14);
\draw [myedgestyle] (v5) edge (v15);
\draw [myedgestyle] (v11) edge (v15);
\draw [myedgestyle] (v9) edge (v16);
\draw [myedgestyle] (v7) edge (v17);
\draw [myedgestyle] (v6) edge (v17);
\draw [myedgestyle] (v4) edge (v18);
\draw [myedgestyle] (v2) edge (v19);
\draw [myedgestyle] (v8) edge (v19);
\draw [myedgestyle] (v10) edge (v20);
\draw [myedgestyle] (v12) edge (v13);
\end{tikzpicture}

Si aplicaramos nuestro algoritmo a un grafo en donde todas las vallas se intersecan entre s\'i, como las vallas marcadas en azules tienen 1 nodo en el que tienen s\'olo esa valla como significado , se eliminar\'ian despu\'es de ejecutar el procedimiento $\texttt{eliminarVallasFueraDeCiclos}$. Ahora, si ejecutamos el algoritmo que recorre nuestro grafo para obtener el ciclo general, todas las vallas internas son ignoradas, por lo tanto nos estar\'iamos quedando con s\'olo 8 vallas, que son las vallas correspondientes a los lados del cuadrado mas grande, cada una divididas al medio. Como adem\'as despu\'es unimos las vallas contiguas, nos terminamos quedando con s\'olo 4 vallas, aun menos que la cantidad de vallas originales! Por lo que, esto nos hace esperanzar con que la cantidad de vallas se mantiene en un orden constante. 

\vspace{0.5cm}

Veamos si nos podemos convencer un poco m\'as: Supongamos que tenemos un ciclo cualquiera en el que nuestro algoritmo no elimina vallas, ni tiene vallas a ignorar, dicho de otra forma, el peor caso que podri\'amos tener (peor caso en el sentido de que no eliminamos vallas, y por lo tanto, cuando llamemos a nuestro algoritmo para dividir figuras, vamos a tener que recorrer todas las vallas):

\vspace{0.5cm}

 \begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]
\tikzstyle{myedgestyle} = [thick]

\node [mynodestyle] (v1) at (-8,-1) {};
\node [mynodestyle] (v1) at (-2,-1) {};
\node [mynodestyle] (v2) at (-2,0) {};
\node [mynodestyle] (v3) at (-3,0) {};
\node [mynodestyle] (v4) at (-3,1) {};
\node [mynodestyle] (v5) at (-2,1) {};
\node [mynodestyle] at (1,1) {};
\node [mynodestyle] (v9) at (1,-1) {};

\node [mynodestyle] (v6) at (0,1) {};
\node [mynodestyle] (v7) at (0,2) {};
\node [mynodestyle] (v8) at (1,2) {};
\draw [myedgestyle] (v1) edge (v2);
\draw [myedgestyle] (v2) edge (v3);
\draw [myedgestyle] (v3) edge (v4);
\draw [myedgestyle] (v5) edge (v4);
\draw [myedgestyle] (v5) edge (v6);
\draw [myedgestyle] (v6) edge (v7);
\draw [myedgestyle] (v7) edge (v8);
\draw [myedgestyle] (v8) edge (v9);
\draw [myedgestyle] (v9) edge (v1);

\end{tikzpicture}

\vspace{0.5cm}

Si a\~nadimos una valla de modo que se interseque con alguna valla del ciclo, podemos tener los siguientes casos:

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]
\tikzstyle{myedgestyle} = [thick]

\node [outer sep=0,inner sep=0,minimum size=0] (v40) at (-5,2) {};

\node [mynodestyle] (v1) at (-2,-1) {};
\node [mynodestyle] (v2) at (-2,0) {};
\node [mynodestyle] (v3) at (-3,0) {};
\node [mynodestyle] (v4) at (-3,1) {};
\node [mynodestyle] (v5) at (-2,1) {};
\node [mynodestyle] at (1,1) {};
\node [mynodestyle] (v9) at (1,-1) {};

\node [mynodestyle] (v6) at (0,1) {};
\node [mynodestyle] (v7) at (0,2) {};
\node [mynodestyle] (v8) at (1,2) {};
\draw [myedgestyle] (v1) edge (v2);
\draw [myedgestyle] (v2) edge (v3);
\draw [myedgestyle] (v3) edge (v4);
\draw [myedgestyle,blue] (v5) edge (v4);
\draw [myedgestyle] (v6) edge (v7);
\draw [myedgestyle] (v7) edge (v8);
\draw [myedgestyle] (v8) edge (v9);

\node [mynodestyle] (v10) at (-1,-2) {};
\node [mynodestyle] (v11) at (-1,2) {};

\node [mynodestyle] (v15) at (2,1) {};
\node [mynodestyle] (v14) at (2,0) {};
\node [mynodestyle] (v13) at (3,0) {};
\node [mynodestyle] (v12) at (3,-1) {};
\node [mynodestyle] (v16) at (5,1) {};
\node [mynodestyle] (v17) at (5,2) {};
\node [mynodestyle] (v18) at (6,2) {};
\node [mynodestyle] (v19) at (6,-1) {};
\draw [myedgestyle] (v12) edge (v13);
\draw [myedgestyle] (v13) edge (v14);
\draw [myedgestyle] (v14) edge (v15);
\draw [myedgestyle] (v15) edge (v16);
\draw [myedgestyle,brown] (v16) edge (v17);
\draw [myedgestyle] (v17) edge (v18);
\draw [myedgestyle] (v18) edge (v19);
\node [mynodestyle] (v20) at (5,-1) {};
\draw [myedgestyle,brown] (v20) edge (v16);
\node [mynodestyle] at (-1,-3) {Caso A};
\node [mynodestyle] at (4,-3) {Caso B};
\node [mynodestyle] (v21) at (-1,-1) {};
\node [mynodestyle] (v22) at (-1,1) {};
\draw[green] [myedgestyle] (v10) edge (v21);
\draw[brown] [myedgestyle] (v21) edge (v22);
\draw[green] [myedgestyle] (v22) edge (v11);
\draw[blue] [myedgestyle] (v5) edge (v22);
\draw[blue] [myedgestyle] (v22) edge (v6);
\node [mynodestyle] (v23) at (4,-1) {};

\draw [myedgestyle,blue] (v12) edge (v20);
\draw [myedgestyle,blue] (v19) edge (v20);
\draw [myedgestyle,blue] (v1) edge (v21);
\draw [myedgestyle,blue] (v21) edge (v9);
\end{tikzpicture}

\vspace{0.5cm}

En el caso A, agregamos una valla que nos divide a la mitad el ciclo (el grafo queda con 9 vallas). Una vez divididas las vallas, obtenemos 13 vallas en total. Pero,las vallas marcadas en verde, son enseguida eliminadas por nuestro algoritmo siguiente, por lo que nos quedamos con 11 vallas. Posteriormente, la valla marcada en marr\'on, es ignorada cuando se recorre el ciclo, por lo tanto pasamos a 10 vallas. De esta forma, a este punto (todav\'ia no unimos las vallas azules en 1 sola) obtenemos 1 valla m\'as por cada valla que agregamos que interseca. De esta forma, en este punto ya tenemos a lo sumo, el doble de vallas que las que ten\'iamos originalmente, por lo que una vez que llamamos al algoritmo \texttt{obtenerContornoCiclo}, si recorremos la vallas, estamos en el mismo orden que originalmente (O(vallas)). Notar que podemos obtener otros casos, como que la valla agregada no la atraviesa completamente, sino que tiene sus extremos en el interior de la figura, o que se interseca en un extremo de la valla agregada en vez de un punto del medio. En todos los casos el razonamiento es an\'alogo. En el caso B, una valla que divide ya pertenec\'ia al ciclo (o sea, se extiende). De nuevo como antes, podr\'iamos tener m\'as casos: que esta valla se extienda de forma que no se interseque con la valla de abajo, o que se interseque en un punto del medio con la valla de abajo. En todos los casos el razonamiento es an\'alogo. Mirando en este ejemplo, tenemos 8 vallas originalmente. Una vez aplicado el algoritmo que divide las vallas, nos quedamos con 10 vallas (la azul queda dividida en 2, y la marr\'on tambi\'en). La valla marr\'on del interior es ignorada por nuestro algoritmo \texttt{obtenerContornoCiclo}, qued\'andonos 9 vallas, como en el caso A. Por lo tanto, podemos asumir que nos quedamos con a lo sumo el doble de vallas tambi\'en. Para el caso en donde tenemos 2 figuras conectadas por los extremos de una valla (que es otro caso en donde tampoco hay vallas extras que elimine nuestro algoritmo en $\texttt{eliminarVallasFueraDeCiclos}$ o \texttt{obtenerContornoCiclo} ), se puede hacer un razonamiento an\'alogo.

\vspace{0.5cm}

De esta forma, si recorremos las vallas despu\'es de llamar a \texttt{obtenerContornoCiclo} lo har\'iamos en el mismo orden que ten\'iamos originalmente, o sea en O(vallas). Para los algoritmos que se encuentran antes de llamar a esta funci\'on, consideraremos que si recorremos todas las vallas, en realidad estamos en un orden cuadr\'atico ( O($vallas^{2}$) ).

\vspace{0.5cm}

Una vez divididas las vallas, creamos el grafo. que es simplemente por cada valla, agregarla al diccionario. Como el diccionario est\'a representado con un HashMap, las operaciones de put, para ingresar las vallas al diccionario son O(1) (asumiendo que nuestra funci\'on de hash dispersa a los elementos apropiadamente). De esta forma, la complejidad de este algoritmo es O(vallas), que como dijimos anteriormente, al considerar que tenemos una cantidad de vallas\_originales$^{2}$, la complejidad nos quedar\'ia en O(vallas$^{2}$)

\vspace{0.5cm}

Posteriormente, llamamos a $\texttt{eliminarVallasFueraDeCiclos}$, en donde recorremos todos los objetos Vallas del diccionario, y eliminamos aquellos nodos con 1 o 0 vallas. Nuevamente, las operaciones de get y remove dentro del ciclo son O(1) al ser un hashmap, por lo que estamos en el mismo orden que antes, O(vallas$^{2}$). Pero, antes de realizar esto, como hab\'iamos contado en la secci\'on desarrollo, tenemos que ordenar los objetos Vallas por la cantidad de vallas que tiene. Como Java implementa la funci\'on sort con un merge sort, esto lo podemos realizar en O(n log(n)), que como estamos en el caso que podr\'iamos estar recorriendo un orden cuadr\'atico de vallas, nos queda $\mathcal{O}(vallas^{2}\log(vallas^{2}))$

\vspace{0.5cm}

 Despu\'es, nuestro algoritmo llama a la funci\'on $\texttt{obtenerCiclosSinSubciclos}$, que hace lo siguiente:

\vspace{0.5cm}

\begin{small}
\begin{algorithmic}[1]
\State Ordenamos la lista de nodos;\Comment{$\mathcal{O}(vallas^{2}\log(vallas^{2}))$}
\For{nodo : grafo} \Comment{$\mathcal{O}(vallas^{2})$}
	\If{El nodo esta en otro ciclo que no recorrimos hasta el momento} \Comment{$\mathcal{O}(vallas)$}
		\State recorrido = $obtenerContornoCiclo(nodo);$ \Comment{$\mathcal{O}(vallas\_componente\_conexa)$}
		\State figuras = $subdividir\_figuras\_por\_aristas(recorrido);$ \Comment{$\mathcal{O}(vallas\_comp\_conexa^{3})$}
		\For{Figura : figuras}
			\State dividirEnRectangulos(figura); \Comment{$\mathcal{O}(vallas\_figura^{3})$}
		\EndFor \Comment{$\mathcal{O}(vallas\_componente\_conexa^{3})$}
	\EndIf
\EndFor \Comment{$\mathcal{O}(vallas^{3})$}
\end{algorithmic}
\bigskip
\end{small}

\vspace{0.5cm}

Veamos en detalle cada l\'inea. Veamos cu\'anto es la cantidad de nodos de nuestro grafo. Por cada valla, tenemos 2 nodos, por lo tanto, si nuestro grafo tiene n vallas, va a tener como mucho 2*n nodos (puede ser menor porque algunas vallas pueden compartir un nodo). De esta forma, si recorremos los nodos, podemos considerar que estamos recorriendo las vallas y el orden no cambia. Entonces, al ordenar la lista de nodos en la l\'inea 1, la complejidad es O(n log n). Como ten\'iamos vallas$^{2}$, nos queda $\mathcal{O}(vallas^{2}\log(vallas^{2}))$. En este punto nos gustar\'ia aclarar que esto se podr\'ia haber hecho m\'as eficiente y recorrer una cantidad menor de nodos: si antes de llamar a nuestra funci\'on inicial que divide las vallas nos hubi\'eramos guardado en una estructura aparte, una lista con los nodos originales , llegados a este punto, \'ibamos a estar s\'olo recorriendo O(vallas), y el algoritmo siguiente no se ver\'ia afectado ya que estar\'iamos recorriendo todas las componentes conexas de todas formas, y el nodo m\'as cercano al origen ser\'ia el mismo que antes. En la l\'inea 3, chequeamos que el nodo que agarramos, no lo hayamos recorrido anteriormente ($\mathcal{O}(vallas)$), y que no este en el interior de algunos de los rect\'angulos hallados ($\mathcal{O}(vallas)$). De esta forma, como esto lo hacemos para cada nodo, en este punto ya estamos en la complejidad requerida por los docentes: $\mathcal{O}(vallas^{2} \cdot vallas)$ = $\mathcal{O}(vallas^{3})$. En la l\'inea 4, se llama al algoritmo que recorre el grafo para quedarse con el ciclo al cual le tenemos hallar la superficie. Si vemos el pseudocodigo realizado en la secci\'on Desaorrollo es f\'acil ver que esta funci\'on s\'olo recorre las vallas del contorno, y por lo tanto, es {$\mathcal{O}(vallas\_componente\_conexa)$}. Vale aclarar que a lo sumo se recorrer\'ia el doble de las vallas del contorno, si hay muchas vallas conectadas, en las cuales en un extremo tienen una figura, y en el otro extremo otra figura, como el ejemplo anteriormente visto (de todas formas, el orden es el mismo):

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node[mynodestyle] (v1) at (-3,1) {};
\draw plot coordinates{(2,1) (2,2) (3,2) (3,1) (1,1) (1,3) (8,3) (8,1) (6,1) (6,2) (7,2) (7,1)};
\end{tikzpicture}

\vspace{0.5cm}

Una vez hecho esto, llamamos a la funci\'on que nos divide en las distintas figuras que pueden estar unidas por extremos de vallas (linea 5). Busquemos una cota un poco ``burda'' y supongamos que en esta funci\'on, tenemos el peor caso. Es decir, que en cada llamada recursiva, s\'olo eliminamos 1 valla y las figuras nos quedan separadas de forma que una figura tiene 4 vallas (menor caso posible), y la otra figura el resto de las vallas. Como en cada llamada recursiva tenemos 2 for anidados, en el que vemos si una valla se repite, el costo extra de la funci\'on es O(vallas$^{2}$). La primera vez que la llamamos, podemos tener a lo sumo n$^{2}$ iteraciones (donde n es la cantidad de vallas..en realidad un poco menos, ya que si tenemos las n$^{2}$ iteraciones quiere decir que no hubo vallas repetidas, y termina, pero como dijimos, hag\'amosla un poco ``burda'' para simplificar cuentas). En el llamado recursivo, podemos tener a lo sumo (n-4) iteraciones, en el siguiente llamado (n-8), en el siguiente (n-12) y as\'i sucesivamente. Por lo tanto, tenemos $\displaystyle\sum_{i=0}^{n/4} (n-4i)^{2} = \frac{1}{12}n(n+2)(n+4)$, lo cual nos da un orden c\'ubico con respecto a la cantidad de vallas de la componente conexa. Para el c\'alculo de funci\'on siguiente (l\'inea 7) podemos realizar exactamente el mismo razonamiento, ya que el costo extra de la funci\'on es el mismo (O(n$^{2}$)), y en los llamados recursivos tenemos el mismo peor caso de ir reduciendo de a 4 vallas (en realidad de a 3 para el caso de esta funci\'on, pero el orden es el mismo...en el c\'odigo se detalla como comentario cu\'anto cuesta cada l\'inea). Como esto lo hacemos para cada figura que se encontraba en la componente conexa, y las figuras son disjuntas entre s\'i (no comparten vallas) si tenemos M figuras (vallas\_fig1, vallas\_fig2, ... ,vallas\_figM) en la componente conexa, la cantidad de operaciones ser\'ia: vallas\_fig1$^{3}$ + ... + vallas\_figM$^{3}$ $\leq$ (vallas\_fig1 + ... + vallas\_figM)$^{3}$ = $\mathcal{O}(vallas\_componente\_conexa^{3})$. El mismo razonamiento podemos hacer para el for general: Si tenemos un grafo con M componentes conexas (vallas\_comp1, vallas\_comp2, ... ,vallas\_compM), y por cada componente conexa del grafo, hallar la superficie de la componente i (con 0 $\leq$ i $\leq$ M) nos cuesta vallas\_compi$^{3}$, entonces, la cantidad de operaciones que necesitamos son: vallas\_comp1$^{3}$ + ... + vallas\_compM$^{3}$ $\leq$ (vallas\_comp1 + ... + vallas\_compM)$^{3}$ = $\mathcal{O}(vallas^{3})$.

\vspace{0.5cm}

De este modo, s\'olo nos resta hallar la superficie de cada rect\'angulo de la figura. Ahora, el algoritmo que sigue es directo: Por cada rect\'angulo, multiplicamos su base por su altura. Pero cu\'antos rect\'angulos obtenemos una vez que dividimos una figura? Si la figura de por s\'i era un rect\'angulo, no se subdivide. Para que sea un rect\'angulo necesita tener 4 vallas. Si queremos a\~nadir un rect\'angulo a nuestra figura, s\'i o s\'i tenemos que a\~nadir 2 vallas. Entonces, tenemos:

\vspace{0.5cm}
{\centering
 
$\textbf{4 vallas } \Rightarrow \textbf{ 1 rectangulo}$\\
$\textbf{ 6 vallas } \Rightarrow \textbf{ 2 rectangulos}$\\
$\textbf{ 8 vallas } \Rightarrow \textbf{ 3 rectangulos}$\\
$\textbf{ 10 vallas } \Rightarrow \textbf{ 4 rectangulos}$\\
$\vdots$\\
$\textbf{ n vallas } \Rightarrow \textbf{ n/2 - 1 rectangulos}$

}

\vspace{0.5cm}

De esta forma, si tenemos n vallas, una vez que ejecutamos todo el algoritmo anterior nos quedan como m\'aximo n/2 - 1 rect\'angulos. Por lo tanto, el costo de este \'ultimo algoritmo es de $\mathcal{O}(vallas)$ y el costo final de todo el algoritmo es de  $\mathcal{O}(vallas^{3})$.

\vspace{0.5cm}

\subsection{Resultados}

A la hora de pensar co\'mo hacer nuestro test de stress, primero tuvimos que pensar de que manera ibamos a tener que ir a\~nadiendo vallas a un grafo inicial. C\'omo deb\'iamos ir cre\'andolas y a\~nadi\'endolas? De forma que se produzca el peor caso posible (osea, tarde lo m\'as posible as\'i nos acercamos al orden hallado), y de forma tal que nos quedara un caso posible (que las vallas no se superpongan en m\'as de un punto, que no tengan extremos en diagonal -o sea, sean todas horizontales o verticales-, o que no est\'en en ejes negativos, a una distancia negativa del molino, por ejemplo). Veamos entonces c\'omo podemos acercarnos al orden hallado. La parte del algoritmo que se m\'as pesada en cuanto a complejidad es cuando dividimos la figura en rect\'angulos. Tener vallas fuera del ciclo, o vallas internas en la figura, lo \'unico que hacen es que nuestro algoritmo mejore ya que las elimina o, directamente no las recorre. Por lo tanto, tenemos que crear un caso de test en donde no se eliminen o ignoren vallas antes de llamar a nuestro algoritmo que divide la figura en rect\'angulos. Ahora, c\'omo creamos ese ciclo/figura, de modo de maximizar el tiempo de corrida de nuestro algoritmo que divide la figura? Esta funci\'on, como vimos, hace llamados recursivos cada vez que encuentra una valla a extender. Si la valla a extender nos divide a la figura en 2 ciclos de aproximadamente n/2 vallas cada uno (con n la cantidad de vallas original), el orden del algoritmo va a ser mucho m\'as eficiente. Por lo tanto, tenemos que tratar de pensar un caso de test que nos divida las figuras, y nos deje en un ciclo, la menor cantidad de vallas posible (que va a ser 4 vallas, ya que es la menor cantidad de vallas que puede tener un ciclo) y el resto de las vallas queden en el otro ciclo. De esta forma, llegamos a nuestro caso de test: una escalera ascendente de cantidad de escalones tan grande como uno quiera. Por ejemplo, una escalera de 3 escalones ser\'ia el siguiente ciclo:

\vspace{0.5cm}

% escalera 
\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v1) at (-2,1) {};
\node [mynodestyle] (v1) at (1,1) {};
\node [mynodestyle] (v2) at (1,3) {};
\node [mynodestyle] (v3) at (3,3) {};
\node [mynodestyle] (v4) at (3,5) {};
\node [mynodestyle] (v5) at (5,5) {};
\node [mynodestyle] (v6) at (5,7) {};
\node [mynodestyle] (v7) at (8,7) {};
\node [mynodestyle] (v8) at (8,5) {};
\node [mynodestyle] (v9) at (6,5) {};
\node [mynodestyle] (v10) at (6,3) {};
\node [mynodestyle] (v11) at (4,3) {};
\node [mynodestyle] (v12) at (4,1) {};
\draw  (v1) edge (v2);
\draw  (v2) edge (v3);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v5) edge (v6);
\draw  (v6) edge (v7);
\draw  (v7) edge (v8);
\draw  (v9) edge (v8);
\draw  (v10) edge (v9);
\draw  (v11) edge (v10);
\draw  (v12) edge (v11);
\draw  (v1) edge (v12);
\end{tikzpicture}

\vspace{0.5cm}

De esta forma, el algoritmo empieza recorriendo el 1er escal\'on, cuando termina de recorrerlo y pasa al segundo escal\'on, se encuentra con que tiene que dividir la figura en 2: en una va a quedar s\'olo el 1er escal\'on, y en la otra figura todos los escalones restantes:

\vspace{0.5cm}

\begin{tikzpicture}
\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]

\node [mynodestyle] (v1) at (1,1) {};
\node [mynodestyle] (v2) at (1,3) {};
\node [mynodestyle] (v3) at (3,3) {};
\node [mynodestyle] (v4) at (3,5) {};
\node [mynodestyle] (v5) at (5,5) {};
\node [mynodestyle] (v6) at (5,7) {};
\node [mynodestyle] (v7) at (8,7) {};
\node [mynodestyle] (v8) at (8,5) {};
\node [mynodestyle] (v9) at (6,5) {};
\node [mynodestyle] (v10) at (6,3) {};
\node [mynodestyle] (v11) at (4,3) {};
\node [mynodestyle] (v12) at (4,1) {};

\node [mynodestyle] (v13) at (7,3) {};
\node [mynodestyle] (v14) at (9,3) {};


\node [mynodestyle] (v15) at (10,0) {};
\node [mynodestyle] (v16) at (10,2) {};
\node [mynodestyle] (v17) at (13,2) {};
\node [mynodestyle] (v18) at (11,5) {};
\node [mynodestyle] (v19) at (13,5) {};
\node [mynodestyle] (v20) at (13,7) {};
\node [mynodestyle] (v21) at (16,7) {};
\node [mynodestyle] (v22) at (16,5) {};
\node [mynodestyle] (v23) at (14,5) {};
\node [mynodestyle] (v24) at (14,3) {};
\node [mynodestyle] (v26) at (11,3) {};
\node [mynodestyle] (v27) at (13,0) {};


\draw (v13) edge[->, very thick] (v14);

\draw (v15) edge (v16);
\draw (v16) edge (v17);
\draw (v27) edge (v17);
\draw (v27) edge (v15);

\draw (v18) edge[<-, thick] (v26);
\draw  (v18) edge[->, thick] (v19);
\draw  (v19) edge[dashed] (v23);
\draw  (v19) edge (v20);
\draw  (v20) edge (v21);
\draw  (v21) edge (v22);
\draw  (v22) edge (v23);
\draw  (v23) edge (v24);
\draw (v24) edge (v26);


\draw  (v1) edge[->, thick] (v2);
\draw  (v2) edge[->, thick] (v3);
\draw (v3) edge[dashed] (v11);
\draw  (v3) edge (v4);
\draw  (v4) edge (v5);
\draw  (v5) edge (v6);
\draw  (v6) edge (v7);
\draw  (v7) edge (v8);
\draw  (v9) edge (v8);
\draw  (v10) edge (v9);
\draw  (v11) edge (v10);
\draw  (v12) edge (v11);
\draw  (v1) edge (v12);
\end{tikzpicture}

\vspace{0.5cm}

El siguiente gr\'afico muestra los resultados obtenidos con el caso de test de estress anterior, ejecutando para cada escalera a nuestro algoritmo unas 10 veces seguidas, y promediando entre las 10 diferentes ejecuciones el tiempo obtenido para bajar el impacto de ejecuciones ``outliers'' (ejecuciones que hayan tardado mucho m\'as por motivos ajenos al algoritmo, como puede ser por el scheduler del sistema operativo).

\vspace{0.5cm}

\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Vallas$,ylabel=tiempo en ms
	]

\addplot[red,domain=1:6500] {x^3/200000000};
\addplot[blue,domain=1:6500] {x^2/40000};
\addplot table {outEj3.txt};

\legend{$x^3/200000000$,$x^{2}/40000$,algoritmo }
\end{axis}
\end{tikzpicture}
\caption{Variaci\'on del tiempo con respecto a la cantidad de vallas del problema.}
\label{}
\end{figure}

\vspace{0.5cm}

En el gr\'afico podemos ver como $x^{3}$ se ``dispara'' en un momento, y empieza a crecer de una manera mucho mas acelerada que nuestro algoritmo y, obviamente, con respecto a $x^{2}$. Por otro lado, nuestro algoritmo, parece mantenerse por debajo de  $x^{2}$ y tener un orden cuadr\'atico. Por qu\'e puede ser esto si la complejidad era del orden c\'ubico? En principio, nuestro test no creemos que sea del todo el peor caso posible, aunque tratamos de que se aproxime en cierto modo como dijimos anteriormente. Visto esto, nos pusimos a re-pensar..podr\'iamos relizar un test que empeore el run-time aun m\'as? Que est\'e por arriba de n$^{2}$? Y efectivamente, despues de estudiar un poco mas en profundidad la complejidad de nuestro algoritmo y nuestro test, pudimos llegar al resultado deseado. Supongamos que tenemos una figura en forma de espiral:

\vspace{0.5cm}

\begin{tikzpicture}

\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]


\node [mynodestyle] (v21) at (-2,-4) {};
\node [mynodestyle] (v1) at (1,-4) {};
\node [mynodestyle] (v2) at (1,4) {};
\node [mynodestyle] (v3) at (9,4) {};
\node [mynodestyle] (v4) at (9,-4) {};
\node [mynodestyle] (v18) at (2,-4) {};
\node [mynodestyle] (v17) at (2,3) {};
\node [mynodestyle] (v16) at (8,3) {};
\node [mynodestyle] (v15) at (8,-3) {};
\node [mynodestyle] (v5) at (3,-4) {};
\node [mynodestyle] (v6) at (3,2) {};
\node [mynodestyle] (v7) at (7,2) {};
\node [mynodestyle] (v8) at (7,-2) {};
\node [mynodestyle] (v9) at (5,-2) {};
\node [mynodestyle] (v10) at (5,0) {};
\node [mynodestyle] (v11) at (6,0) {};
\node [mynodestyle] (v12) at (6,1) {};
\node [mynodestyle] (v13) at (4,1) {};
\node [mynodestyle] (v14) at (4,-3) {};
\node [mynodestyle] (v19) at (7,0) {};


\draw  (v1) edge[->,thick] (v2);
\draw  (v2) edge[->,thick] (v3);
\draw  (v3) edge[->,thick] (v4);
\draw  (v4) edge[->,thick] (v5);
\draw  (v5) edge[->,thick] (v6);
\draw  (v6) edge[->,thick] (v7);
\draw  (v7) edge[->,thick] (v8);
\draw  (v8) edge[->,thick] (v9);
\draw  (v9) edge[->,thick] (v10);
\draw  (v10) edge[->,thick] (v11);
\draw (v11) edge[dashed] (v19);
\draw  (v10) edge (v11);
\draw  (v11) edge (v12);
\draw  (v12) edge (v13);
\draw  (v13) edge (v14);
\draw  (v14) edge (v15);
\draw  (v15) edge (v16);
\draw  (v16) edge (v17);
\draw  (v17) edge (v18);
\draw  (v18) edge (v1);
\end{tikzpicture}

\vspace{0.5cm}

Como vemos, hasta que se encuentra una valla a extender, tiene que recorrer aproximadamente la mitad de las vallas (comparado al test con la escalera, en donde en la 2da iteraci\'on ya encontraba una valla a extender) y por lo tanto, c\'omo encontrar la valla que interseca a la valla que se extiende es tambi\'en aproximadamente n/2, el costo extra de la funci\'on (sin los llamados recursivos) va a ser O(n$^{2}$) en vez de O(n) como era en el test con la escalera. Una vez que la encuentra, la figura queda dividida de forma similar al caso anterior: un ciclo de 4 vallas, y un ciclo con las vallas restantes (m\'as una) de la siguiente forma:


\vspace{0.5cm}

\begin{tikzpicture}

\tikzstyle{mynodestyle} = [outer sep=0,inner sep=0,minimum size=0]


\node [mynodestyle] (v21) at (-2,-4) {};
\node [mynodestyle] (v1) at (1,-4) {};
\node [mynodestyle] (v2) at (1,4) {};
\node [mynodestyle] (v3) at (9,4) {};
\node [mynodestyle] (v4) at (9,-4) {};
\node [mynodestyle] (v18) at (2,-4) {};
\node [mynodestyle] (v17) at (2,3) {};
\node [mynodestyle] (v16) at (8,3) {};
\node [mynodestyle] (v15) at (8,-3) {};
\node [mynodestyle] (v5) at (3,-4) {};
\node [mynodestyle] (v6) at (3,2) {};
\node [mynodestyle] (v7) at (7,2) {};
\node [mynodestyle] (v8) at (7,-2) {};
\node [mynodestyle] (v9) at (5,-2) {};
\node [mynodestyle] (v10) at (5,0) {};
\node [mynodestyle] (v11) at (6,0) {};
\node [mynodestyle] (v12) at (6,1) {};
\node [mynodestyle] (v13) at (4,1) {};
\node [mynodestyle] (v14) at (4,-3) {};
\node [mynodestyle] (v19) at (7,0) {};
\node [mynodestyle] (v20) at (6,2) {};

\draw  (v1) edge[->,thick] (v2);
\draw  (v2) edge[->,thick] (v3);
\draw  (v3) edge[->,thick] (v4);
\draw  (v4) edge[->,thick] (v5);
\draw  (v5) edge[->,thick] (v6);
\draw  (v6) edge[->,thick] (v7);
\draw (v11) edge[<-,thick] (v19);
\draw (v7) edge[->,thick] (v19);
\draw (v11) edge[dashed] (v20);
\draw  (v11) edge[->,thick]  (v12);
\draw  (v12) edge (v13);
\draw  (v13) edge (v14);
\draw  (v14) edge (v15);
\draw  (v15) edge (v16);
\draw  (v16) edge (v17);
\draw  (v17) edge (v18);
\draw  (v18) edge (v1);
\end{tikzpicture}

\vspace{0.5cm}

Si seguimos el procedimiento de la misma forma, vemos como esto se sigue comportando igual en los llamados recursivos, y por lo tanto, haciendo que el tiempo de ejecuci\'on sea mayor al del caso anterior. Una vez implementado este caso (y a las corridas porque ya estabamos a horas de la entrega del tp!), obtuvimos el siguiente gr\'afico:

\vspace{0.5cm}

\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
    \begin{axis}[
	axis x line=middle,
	xlabel=$\#Vallas$,ylabel=tiempo en ms
	]

\addplot[red,domain=1:2440] {x^3/50000000};
\addplot[blue,domain=1:2440] {x^2/9000};
\addplot table {outEj32.txt};
\addplot[mark=ball] table {outEj3E.txt};

\legend{$x^3/50000000$,$x^{2}/9000$,algoritmo con escalera, algoritmo con espiral}
\end{axis}
\end{tikzpicture}
\caption{Variaci\'on del tiempo con respecto a la cantidad de vallas del problema con los 2 tests diferentes.}
\label{}
\end{figure}

\vspace{0.5cm}

Como se ve en el gr\'afico, la curva del nuevo caso de test se asemeja mucho m\'as a la de x$^{3}$, por lo que ahora s\'i parecemos acercarnos al orden c\'ubico obtenido cuando hicimos el an\'alisis te\'orico de la complejidad.

\vspace{0.5cm}


Se midieron, adem\'as, los tiempos en un caso sin ninguna intencionalidad en particular.
El gr\'afico que compara la complejidad calculada con los resultados obtenidos al correr el programa es el siguiente:

\vspace{1cm}

\begin{figure}[here]
\begin{tikzpicture}
\pgfplotsset{every axis legend/.append style={
at={(1.02,1)},
anchor=north west}}
     \begin{axis}[
	xlabel=$vallas$,ylabel=$Tiempo (ms)$
	]
	
\addplot table {vallasM.txt};
\addplot[red,domain=1:2450] {x^3/80000000};

\legend{Caso sin intenci\'on, $x^3/80000000$}
\end{axis}
\end{tikzpicture}
\caption{Variaci\'on del tiempo con respecto a la cantidad de vallas.}
\label{}
\end{figure}

\vspace{1cm}

\vspace{0.5cm}


El caso consiste en ir agregando 4 vallas por cada iteraci\'on, de manera que quedan formados cuadrados de 1x1, uno junto a otro o separados entre s\'i. 
Las ventajas que tiene este caso para que resulte m\'as r\'apido el c\'alculo de la superfie son:
\begin{itemize}
\item Cuando los cuadrados quedan unidos, se forman subciclos, por lo que se descartan la vallas internas. 
\item Todos los ciclos forman cuadrados o rect\'angulos, as\' que se evita que el algoritmo extienda vallas y divida la figura.
\item Algunas vallas agregadas son de menor altura que el l\'imite que saltan las langostas. Son vallas para descartar.    
\item Vallas dispersas que no forman ciclos. 
\end{itemize}

Como era de esperarse, por todo lo mencionado anteriormente, la curva obtenida queda muy por debajo de la de la complejidad calculada. 

\newpage


\subsection{Conclusiones}

!`Qu\'e decir de este problema! Dimos las mil y un vueltas con \'el, pasamos de una implementaci\'on sin funcionar en base a un grafo dirigido (con la cual comenzamos porque cre\'iamos que de esa forma iba a ser mas eficiente y f\'acil de resolver) a una implementaci\'on con un grafo no dirigido, que modelaba mejor el problema, pero que inicialmente nuestro algoritmo no funcionaba para todos los casos. Estamos conformes con la soluci\'on obtenida y mucho m\'as a\'un, con todo el proceso de an\'alisis que nos llev\'o a ella (las decenas de grafos que dibujamos en papel, las decenas de conclusiones, algunas que parec\'ian verdaderas - hasta que encontr\'abamos un grafo que no la cumpl\'ia -, y otras que eran verdaderas pero que nos costaban creer al comienzo, etc). Y despu\'es con el tema de la complejidad! Que daba, que no daba, que volv\'ia a dar, y que volv\'ia a no dar...!`Que susto nos dimos cuando vimos que una vez que divid\'iamos las vallas al comienzo de nuestro algoritmo nos quedaba un orden de O(vallas$^{2}$)!. En conclusi\'on, el problema nos ayudo much\'isimo a ``abrir la cabeza'' (capaz que en parte gracias a todas las veces que nos dimos ``la cabeza contra la pared'' =P) y a aprender a c\'omo enfrentarnos cuando tenemos un problema de grafos m\'as complejo, y que no encaja con los algoritmos vistos en clase (de caminio minimo por ejemplo). Adem\'as, gracias a este problema tambi\'en, aprendimos como se usa (aunque sea lo b\'asico!) el paquete de latex llamado ``Tikz'', que nos sirvi\'o para realizar los diferentes gr\'aficos que nos ayudaron a exponer nuestro algoritmo. 

\newpage

\section{Referencias}

\begin{thebibliography}{99} 
\bibitem{java} JavaTM 2 Platform, Standard Edition, v 1.4.2 API Specification (http://docs.oracle.com/javase/1.4.2/docs/api/)


\end{thebibliography}

\end{document}


